6.841/18.405J: Advanced Complexity Theory
Prereq: 6.840
Time: MW 11:0012:30pm
Location:
2147
309 HLevel Grad Credit
Homepage:
http://theory.lcs.mit.edu/~madhu/ST02/
Combined notes for all lectures:
(ps,
gzipped ps,
pdf)
Problem sets
Lectures:

Lecture 01 (2/06):
Introduction. Review of Complexity:
Reductions, Time, Space, Nondeterminism.
Slides
(ps,
pdf).
Notes
(ps,
pdf).

Lecture 02 (2/11):
Relativization. BakerGillSolovay. Introduction
to Alternation. Slides
(ps,
pdf).
Notes
(ps,
pdf).

Lecture 03 (2/13):
Alternation. ATIME vs. SPACE, ASPACE vs. TIME.
Slides
(ps,
pdf).
Notes
(ps,
pdf).

Lecture 04 (2/19):
Power of Alternation: Fortnow's Time/Space lower bound.
The Polynomial Hierarchy.
Slides
(ps,
pdf).
Preliminary notes
(ps,
pdf).

Lecture 05 (2/20):
The PH Collapse hypothesis.
Nonuniform computations. KarpLipton theorem.
Slides
(ps,
pdf).
Notes
(ps,
pdf).

Lecture 06 (2/25):
Randomness. Randomized complexity classes.
Sample problems in RP, RL.
Slides
(ps,
pdf).
Notes
(ps,
pdf).

Lecture 07 (2/27):
Amplification of error in Randomness.
BPP in P/poly. BPP in PH.
Slides
(ps,
pdf).
Notes
(ps,
pdf).

Lecture 08 (3/04):
Circuit lower bounds: Parity is not in AC0.
Slides
(ps,
pdf).
Notes
(ps,
pdf).

Lecture 09 (3/06):
SAT reduces probabilistically to Unique SAT.
Counting classes.
Slides
(ps,
pdf).
Notes
(ps,
pdf).

Lecture 10 (3/11):
Toda's theorem: PH is contained in #P.
Slides
(ps,
pdf).
Notes
(ps,
pdf).

Lecture 11 (3/13): Guest Lecturer: Dan Spielman.
Toda's theorem (contd.).
Slides
(ps,
pdf).
Notes
(ps,
pdf).

Lecture 12 (4/01):
Proofs. Interactive Proofs, Arthur Merlin games.
Slides
(ps,
pdf).
Notes
(ps,
pdf).

Lecture 13 (4/03):
IP in PSPACE; AM[poly] = IP[poly]; AM[k] = IP[k];
Slides
(ps,
pdf).
Preliminary notes
(ps,
pdf).

Lecture 14 (4/08):
#P is in IP; Straightline programs of polynomials; IP = PSPACE;
Slides
(ps,
pdf).
Notes
(ps,
pdf).

Lecture 15 (4/10):
Probabilistically checkable proofs (PCP).
Slides
(ps,
pdf).
Preliminary notes
(ps,
pdf).

Lecture 16 (4/17):
NP in PCP(polylog,polylog).
Slides
(ps,
pdf).
Preliminary notes
(ps,
pdf).

Lecture 17 (4/22):
NP in PCP(polylog,polylog) (contd.)
Slides (See slides for Lecture 16).
Preliminary notes
(ps,
pdf).

Lecture 18 (4/24):
Overview of the PCP Theorem. NP is in PCP[poly(n), O(1)].
Preliminary notes
(ps,
pdf).

Lecture 19 (4/29):
Average case complexity. Hardness of the permanent
on random instances. Distributed NP.
Preliminary notes
(ps,
pdf).

Lecture 20 (5/01):
DNP. AvgP. A problem complete for psampleable DNP problems.
Preliminary notes
(ps,
pdf).

Lecture 21 (5/06):
A DNPcomplete problem (contd.).
Ajtai's worstcase to average case connection for
lattice problems.
Slides
(ps,
pdf).
Preliminary notes
(ps,
pdf).

Lecture 22 (5/08):
Quantum information, manipulation and computation.
Quantum circuits and Turing machines.
Preliminary notes (we had two scribes for this lecture):
First set (ps,
pdf),
Second set (ps,
pdf).

Lecture 23 (5/13):
Quantum Polynomial time (BQP). Simon's algorithm. Shor's algorithm.
Preliminary notes (we'll have two scribes for this lecture):
First set (ps,
pdf),
Second set (ps,
pdf).

Lecture 24 (5/15):
Quantum computation wrapup. Summary.
Preliminary notes
(ps,
pdf).
The course covered several current directions of
research in Complexity Theory.
One glaring omission, intentionally, is the work
related to pseudorandomness and derandomization.
The right way to learn about these topics is to attend
the Harvard course on
Pseudorandomness,
being taught by
Salil Vadhan.
References.
I'll try to add more as time passes.
Instructor:
Madhu Sudan.