Course announcement: Advanced Complexity Theory (6.841/18.405) -
Time: MW 11-12:30
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
Lecture notes for this course from Spring 2005 give further details on
the material covered. These may be found at
- Review of time and space complexity.
- Non-determinism and alternation.
- Non-uniform models of computation and lower bounds.
- Interaction, proof, and knowledge.
- Probabilistically checkable proofs and Inapproximability.
- Quantum computation.
Instructor: Madhu Sudan