Advanced
Complexity Theory
(MIT 6.841J/18.405J; Spring 2009)
General
Info:
- Lecturer: Madhu Sudan;
32-G640; email: first name at mit dot edu
- TA:
Brendan Juba;
32-G636; email: bjuba at mit dot edu; Office Hours: TBA
- Units:
3-0-9 H Level Grad Credit;
-
Time and Location: MW 11-12:30 in 26-322
Announcements:
Tentative
list of Topics:
- Lecture 01 (02/04): Introduction. Review of Complexity. Notes. Scribe notes (lect01.tex, lect01.pdf).
- Lecture 02 (02/09): Diagonalization and Relativization. Ladner's
theorem. Notes. Scribe notes (lect02.tex, lect02.pdf).
- Lecture 03 (02/11): Non-uniform complexity. Neciporuk's Lower
Bound for Formula Size. Notes.
Scribe notes (lect03.tex, lect03.pdf).
- Monday 02/16: Presidents Day
Holiday.
- Lecture 04 (02/17): MIT
Virtual Monday!
Barrington's theorem. Notes.
Scribe notes (lect04.tex, lect04.pdf).
- Lecture 05 (02/18): Parity is not in AC0 (Furst-Saxe-Sipser). Notes. Scribe notes (lect05.tex, lect05.pdf).
- Lecture 06 (02/23): Parity is not in AC0 (Razborov-Smolensky). Notes. Scribe notes (lect06.tex, lect06.pdf).
- Lecture 07 (02/25): Communication Complexity and Circuit lower
bounds. Notes. Scribe notes (lect07.tex, lect07.pdf).
- Lecture 08 (03/02): Alternation: Time vs. Space. Fortnow's
theorem. Notes. Scribe notes (lect08.tex, lect08.pdf).
- Lecture 09 (03/04): Debates, Alternation, Polynomial Hierarchy,
Karp-Lipton theorem. Notes. Scribe
notes (lect09.tex, lect09.pdf).
- Lecture 10 (03/09): Randomness and computing. Algorithms,
Models, Classes, Promise Problems. Notes.
Scribe notes (lect10.tex, lect10.pdf).
- Lecture 11 (03/11): Properties of BPP: Amplification, Low
circuit complexity, Containment in PH. Notes.
Scribe notes (lect11.tex, lect11.pdf).
- Lecture 12 (03/16): Complexity of Unique Satisfiability.
Counting Problems. Notes. Scribes
notes (lect12.tex, lect12.pdf).
- Lecture 13 (03/18): Toda's theorem: Alternation reduces to
counting. Notes. Scribe notes (lect13.tex, lect13.pdf).
- 03/23 - 03/27: Spring Break!
- Lecture 14 (03/30): Interactive Proofs. AM, IP. Notes. Scribe notes (lect14.tex, lect14.pdf).
- Lecture 15 (04/01): IP vs. PSPACE. #P in IP. Notes. Scribe notes (lect15.tex, lect15.pdf).
- Lecture 16 (04/06): Straightline program with polynomials.
IP=PSPACE. Notes. Scribe notes (lect16.tex, lect16.pdf).
- Lecture 17 (04/08): Knowledge, Statistical and Computational. Notes. Scribe notes (lect17.tex, lect17.pdf).
- Lecture 18 (04/13): Probabilistically checkable proofs.
Statement of the PCP theorem. Approximation and Inapproximability.
Scribe notes (lect18.tex, lect18.pdf).
- Lecture 19 (04/15): PCP - An exponentially long, O(1)-query, PCP
for satisfiability. Notes. Scribe
notes (lect19.tex, lect19.pdf).
- Monday 04/20: Patriots Day
Holiday.
- Lecture 20 (04/22): PCP - Dinur's proof of the PCP Theorem (most
of it). Notes. Scribe notes (lect20.tex, lect20.pdf).
- Lecture 21 (04/27): Guest
lecturer: Jakob Nordstrom: Proof Complexity. Notes (joint notes for Lectures 21 and
22): Scribe notes (lect21.tex, lect21.pdf).
- Lecture 22 (04/29): Guest
lecturer: Jakob Nordstrom: Proof Complexity (contd.). Scribe
notes (lect22.tex, lect22.pdf).
- Lecture 23 (05/04): Average case complexity. Notes. Scribe notes (lect23.tex, lect23.pdf).
- Lecture 24 (05/06): CANCELLED
Due to Project Presentations
- Wednesday (05/06):
9am-12:00pm: Project Presentations in G531 (Signup info here).
- Thursday (05/07):
9am-12:30pm: Project Presentations in G631 (Signup info here)
- Lecture 25 (05/11): Pseudorandomness and Derandomization. Notes. Scribe notes (lect25.tex, lect25.pdf).
- Lecture 26 (05/13): Conclusions.
References:
Scribes: