Course announcement: Advanced
Complexity Theory (6.841J/18.405J) -
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
A tentative list of topics is
available from the course website (http://courses.csail.mit.edu/6.841).
- 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.
Lecture notes for this course
from previous semesters give further
the material covered. These may be found at
TA: Brendan Juba