Advanced complexity theory

Lectures: 2 sessions / week, 1.5 hours / session

The formal perquisite is 18.404J / 6.840J Theory of Computation which covers the early chapters of the required textbook book (see below).

However, students who have not taken the above specific course who still have a basic knowledge of complexity theory, either through the MIT undergraduate class 6.045J / 18.400J Automata, Computability, and Complexity, or through another basic course elsewhere, are likely to have enough background to register.

This graduate-level course focuses on current research topics in computational complexity theory. Topics include:

The primary written reference for the course is

Arora, Sanjeev, and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009. ISBN: 9780521424264. [Preview with Google Books]

A draft of Computational Complexity: A Modern Approach is available online free of charge, but the latest edition contains corrections and improvements.

There will be 4 (small) problem sets during the semester with two or three problems in each set. These will be due at the beginning of class roughly two weeks after their assignment. Please observe the following:

Each registered student is expected to participate in grading one of the four problem sets. The graders will receive a model solution, and are expected to submit the graded solutions within a week.

Each problem part should be marked as either: (3) Perfect solution; (2) Mostly correct solution but with minor mistakes; (1) A very flawed solution with some correct ideas; or (0) Missing / completely wrong solution.

Concrete mistakes should be marked and explained. The purpose is that the students get a fair and useful feedback on their solutions.

The grader will receive a score on their performance based the overall quality, precision, and fairness of their grading.

Students will work individually or in pairs to complete a written final project. The final projects must be in the form of an in-depth literature review, highlighting a firm understanding of an important development or idea in complexity theory.

The choice of topic and relevant paper(s) must be done with coordination of the instructors, and receive a formal approval.

Timeline of the project is as follows:

There will be a limited number of slots available during the last week of the class for the presentation of the projects. Unlike the written survey (which is required), presentation of the final projects is voluntary. A satisfactory presentation of a well-done project counts as a strong bonus in our evaluation of students' performance, and is strongly recommended to students with keen interest in further research in complexity theory.

We will use Piazza (a Q&A web service) for questions and answers during the semester. Note: Not available to OCW users.

The final grade will be based on four small problem sets, a grading assignment, and a final project.

The grading breakdown is as follows:

Don't show me this again

This is one of over 2,200 courses on OCW. Find materials for this course in the pages linked along the left.

MIT OpenCourseWare is a free & open publication of material from thousands of MIT courses, covering the entire MIT curriculum.

No enrollment or registration. Freely browse and use OCW materials at your own pace. There's no signup, and no start or end dates.

Knowledge is your reward. Use OCW to guide your own life-long learning, or to teach others. We don't offer credit or certification for using OCW.

Made for sharing. Download files for later. Send to friends and colleagues. Modify, remix, and reuse (just remember to cite OCW as the source.)

Learn more at Get Started with MIT OpenCourseWare