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

Prereq: 6.840.
Time: MW 11-12:30
Location: 26-322
3-0-9 H-Level Grad Credit
Homepage: http://theory.csail.mit.edu/~madhu/ST07/ 

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.
Lecture notes for this course from Spring 2005 give further details on the material covered. These may be found at
http://theory.lcs.mit.edu/~madhu/ST05/

Instructor: Madhu Sudan