## Course announcement: Advanced
Complexity Theory (6.841J/18.405J) -
Spring 2009

Prereq: 6.840J/18.404J

Time: MW 11-12:30

Location: 26-322

3-0-9 H-Level Grad Credit

Homepage: http://courses.csail.mit.edu/6.841

# 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.
- Non-uniform models of computation and lower bounds.
- Interaction, proof, and knowledge.
- Probabilistically checkable proofs and inapproximability.

- Quantum computation.

A tentative list of topics is
available from the course website (http://courses.csail.mit.edu/6.841).

Lecture notes for this course
from previous semesters give further
details on
the material covered. These may be found at

http://people.csail.mit.edu/madhu/ST02,
http://people.csail.mit.edu/madhu/ST03,
http://people.csail.mit.edu/madhu/ST05,
and http://people.csail.mit.edu/madhu/ST07.

Instructor:
Madhu Sudan
TA: Brendan Juba