15-453 Formal Languages, Automata and Computation
Spring 2014, TTH 12:00-1:20, GHC 4215


[Schedule/Assignments | Project Info | What's New?]


PROJECT Presentations

PROJECT list: Post title, View list




The primary goal of this project is to give you an idea of what it feels like to do research in theoretical computer science. You are expected to obtain an in-depth understanding of a specific topic, and be able to hold educated conversations with experts in the field. You are free to choose your topic (although it must be approved by the course instructors). The project will count for 15% of your final grade in this class.


What you need to do

The first step is to choose a topic. This is not an easy thing to do, so we recommend spending time interacting with the instructor/TAs as well as researching what topic to choose. At the bottom of this handout, we present suggestions for places to look for project ideas. You can take any of our suggestions or work on a project of your own design (this is recommended if and only if you have had research experience with a specific problem that has a theoretical computer science component to it). You cannot choose a topic that somebody else has already chosen (this will be decided on a first-come first-serve basis when you talk to the instructors about your topic). After choosing a topic, you are expected to learn as much as you can regarding your topic, and are encouraged (although not required nor expected) to make original research contributions. You will hand in two write-ups of what you have accomplished so far (see below for specific deadlines).


  • The first write-up will consist mostly of the statement of the problem that you will investigate with references; subsequent write-ups should get longer as the semester progresses.
  • The second write-up will consist of a detailed outline or first draft of your final report.
  • The final write-up should be a maximum of 10 pages long, and should be a coherent explanation of the problem and everything you understand about it. This should be accompanied by a Poster.
  • At the end of the semester, you will be required to give an 5-10 minute Presentation with Poster about your project to an audience consisting of other students in the class, the instructors and graduate students in theoretical computer science.


Throughout the semester, you are also expected to schedule a meeting with an instructor/TA at least once a month to talk about your project freely. You should be ready to answer any questions the instructor/TA might have on the topic.


What you need to do

  • Choose a (unique) topic
  • Learn as much as you can about your topic
  • Schedule meetings with an instructor once a month
  • Write progress reports
  • Prepare a final 10-minute in-class presentation


Important dates

  • February 6. First progress report due (this should essentially be an explanation of the problem you will investigate throughout the semester).
  • March 22. Second progress report due.
  • April 24 and April 29 (perhaps also May 1). In-class presentations.
  • May 1. Final project report due.


Suggested places to look for project topics

  • Any paper that has appeared in the Proceedings of FOCS or STOC in the last 5 years. FOCS (Foundations of Computer Science) and STOC (Symposium on the Theory of Computing) are the two major conferences of general computer science theory. The proceedings of both conferences are available at the E&S library or electronically:

Electronic version of the proceedings of STOC

Electronic version of the proceedings of FOCS


  • Here are 2 relevant blogs:


Theory of Computing Blog Aggregator