Advanced Complexity Theory (6.841J/18.405J)

Course number: 6.841 J/18.405J
Prereq: 6.840
Time: MW 11:00-12:30pm
Location: 26-322
3-0-9 H-Level Grad Credit
Lecturer: Madhu Sudan
TA: Swastik Kopparty
Homepage: http://theory.csail.mit.edu/~madhu/ST07

Bulletin Board

Please fill out the "Undergraduate Guide" Evaluation!!

Grading policy.
We're adding a forum for discussions at mit6841.blogspot.com.
Please do make use of it to raise questions about the course material.
List of projects is now available. Please start scanning the topics and make sure
you have chosen one before spring break.

Course announcement

Tentative list of Topics:

Lecture 01 (02/07): Introduction. Review of Complexity. Notes. Scribe notes (lect01.tex, lect01.pdf).
Lecture 02 (02/12): Diagonalization and Relativization. Ladner's theorem. Notes. Scribe notes (lect02.tex, lect02.pdf).
Lecture 03 (02/14): Non-uniform complexity. Neciporuk's Lower Bound for Formula Size. Notes. Scribe notes (lect03.tex, lect03.pdf).
Monday 02/19: Presidents Day Holiday.
Lecture 04 (02/20): MIT Virtual Monday! Barrington's theorem. Notes. Scribe notes (lect04.tex, lect04.pdf).
Lecture 05 (02/21): Parity is not in AC0 (Furst-Saxe-Sipser). Notes. Scribe notes (lect05.tex, lect05.pdf).
Lecture 06 (02/26): Parity is not in AC0 (Razborov-Smolensky). Notes. Scribe notes (lect06.tex, lect06.pdf).
Lecture 07 (02/28): Communication Complexity and Circuit lower bounds. Notes. Scribe notes (lect07.tex, lect07.pdf).
Lecture 08 (03/05): Alternation: Time vs. Space. Fortnow's theorem. Notes. Scribe notes (lect08.tex, lect08.pdf).
Lecture 09 (03/07): Debates, Alternation, Polynomial Hierarchy, Karp-Lipton theorem. Notes. Scribe notes (lect09.tex, lect09.pdf).
Lecture 10 (03/12): Randomness and computing. Algorithms, Models, Classes, Promise Problems. Notes. Scribe notes (lect10.tex, lect10.pdf).
Lecture 11 (03/14): Properties of BPP: Amplification, Low circuit complexity, Containment in PH. Notes. Scribe notes (lect11.tex, lect11.pdf).
Lecture 12 (03/19): Complexity of Unique Satisfiability. Counting Problems. Notes. Scribes notes (lect12.tex, lect12.pdf).
Lecture 13 (03/21): Toda's theorem: Alternation reduces to counting. Notes. Scribe notes (lect13.tex, lect13.pdf).
03/26 - 03/30: Spring Break!
Lecture 14 (04/02): Interactive Proofs. AM, IP. Notes. Scribe notes (lect14.tex, lect14.pdf).
Lecture 15 (04/04): IP vs. PSPACE. #P in IP. Notes. Scribe notes (lect15.tex, lect15.pdf).
Lecture 16 (04/09): Straightline program with polynomials. IP=PSPACE. (No notes.) Scribe notes (lect16.tex, lect16.pdf).
Lecture 17 (04/11): Knowledge, Statistical and Computational. Notes. Scribe notes (lect17.tex, lect17.pdf).
Monday 04/16: Patriots Day Holiday.
Lecture 18 (04/18): Probabilistically checkable proofs. Statement of the PCP theorem. Approximation and Inapproximability. Scribe notes (lect18.tex, lect18.pdf).
Lecture 19 (04/23): PCP - An exponentially long, O(1)-query, PCP for satisfiability. Notes. Scribe notes (lect19.tex, lect19.pdf).
Lecture 20 (04/25): PCP - Dinur's proof of the PCP Theorem (most of it). Notes. Scribe notes (lect20.tex, lect20.pdf).
Lecture 21 (04/30): Average case complexity: Definitions. Notes. Scribe notes (lect21.tex, lect21.pdf).
Lecture 22 (05/02): Average case complexity: A DNP complete problem. Notes. Scribe notes (lect22.tex, lect22.pdf).
Lecture 23 (05/07): Average case complexity - III. problem. Scribe notes (lect23.tex, lect23.pdf).
Lecture 24 (05/09): CANCELLED Due to Project Presentations
Wednesday (05/09): 9am-12:30pm: Project Presentations in G531 (Signup info here).
Thursday (05/10): 9am-12:30pm: Project Presentations in G631 (Signup info here)
Lecture 25 (05/14): Quantum computing.
Lecture 26 (05/16): Conclusions.

References:

Dan Spielman's Lecture Notes from Spring 2001 http://www-math.mit.edu/~spielman/AdvComplexity/2001.
Lecture Notes from Spring 2005 http://theory.lcs.mit.edu/~madhu/ST05. (Can also try .../ST02, .../ST03 for interim years' notes.)
Oded Goldreich's book: Computational Complexity: A Conceptual Perspective. (Draft)
Christos Papadimitriou's text: Computational Complexity.
Michael Sipser's text: Introduction to the Theory of Computation (for initial lectures only).

Scribes:

Availability information here.
Sample tex file, uses preamble.tex and fullpage.sty.