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

Prereq: 6.840.
Time: MW 1-2:30
Location: 32-124
3-0-9 H-Level Grad Credit

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. Randomized computation and derandomization.
  4. Non-uniform models and lower bounds.
  5. Interaction, proof, and knowledge.
  6. Quantum computation.
Lecture notes for this course from Spring 2003 give further details on the material covered. These may be found at

Instructor: Madhu Sudan