Course announcement: Advanced Complexity Theory (6.841/18.405) -
Time: MW 1-2: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 2003 give further details on
the material covered. These may be found at
- Review of time and space complexity.
- Non-determinism and alternation.
- Randomized computation and derandomization.
- Non-uniform models and lower bounds.
- Interaction, proof, and knowledge.
- Quantum computation.
Instructor: Madhu Sudan