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

- Please fill out HKN Survey (even if you are only a listener).

- Course announcement
- Grading Policy
- Problem Sets: Instructions;
PS1, PS2,
PS3.

- Scribe availability (Sample files for scribes: sample.tex; Uses: preamble.tex and fullpage.sty)
- Project 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.

- Dan Spielman's Lecture Notes from Spring 2001 http://www-math.mit.edu/~spielman/AdvComplexity/2001.
- Lecture Notes from Spring 2007 http://theory.lcs.mit.edu/~madhu/ST07. (Can also try .../ST02, .../ST03, .../ST05 for interim years' notes.)
- Oded Goldreich: Computational Complexity: A Conceptual
Perspective.

- Sanjeev Arora and Boaz Barak: Computational Complexity: A Modern Approach.
- Christos Papadimitriou: Computational Complexity.
- Michael Sipser: Introduction to the Theory of Computation (for initial lectures only).

- Availability information here.

- Sample tex file, uses preamble.tex and fullpage.sty.