Course announcement: Advanced Complexity Theory (6.841J/18.405J) - Spring 2009

Prereq: 6.840J/18.404J
Time: MW 11-12:30
Location: 26-322
3-0-9 H-Level Grad Credit
Homepage: http://courses.csail.mit.edu/6.841

Advanced Complexity Theory

This course is a follow-up to Introduction to the theory of computation (6.840). It covers advanced topics in computational complexity, leading up to the state-of-the-art in the field. Principal topics include:
  1. Review of time and space complexity.
  2. Non-determinism and alternation.
  3. Non-uniform models of computation and lower bounds.
  4. Interaction, proof, and knowledge.
  5. Probabilistically checkable proofs and inapproximability.
  6. Quantum computation.
A tentative list of topics is available from the course website (http://courses.csail.mit.edu/6.841).

Lecture notes for this course from previous semesters give further details on the material covered. These may be found at
http://people.csail.mit.edu/madhu/ST02,  http://people.csail.mit.edu/madhu/ST03, http://people.csail.mit.edu/madhu/ST05, and http://people.csail.mit.edu/madhu/ST07.

Instructor: Madhu Sudan   TA: Brendan Juba