Course announcement: Advanced Complexity Theory (6.841)
Prereq: 6.840.
Time: MW 1-2:30
Location: 2-105
3-0-9 H-Level Grad Credit
Homepage: http://theory.lcs.mit.edu/~madhu/ST03/
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:
- 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.
Lecture notes for this course from Spring 2002 give further details on
the material covered. These may be found at
http://theory.lcs.mit.edu/~madhu/ST02/
Instructor: Madhu Sudan