Course Staff
Lecturer: Madhu Sudan
TA: Prahladh Harsha

General Information

Bulletin Board

Problem Sets

Schedule of Lectures:
Lecture 01: (2/05) Introduction, Review of Complexity; Slides (pdf, ps). Notes (tex, ps, pdf).  3/26: Spring Break 
Lecture 02: (2/10) Relativization and Alternation; Slides (pdf, ps). Notes (tex, ps, pdf).  Lecture 13: (3/31) IP=PSPACE; Slides (pdf, ps). Draft of notes (tex, ps, pdf). 
Lecture 03: (2/12) Alternation and Time vs. Space; Slides (pdf, ps). Notes (tex,ps, pdf).  Lecture 14: (4/02) IP = PSPACE. Other models of proofs. PS 3 Due. Slides (pdf, ps). Draft of notes (tex, ps, pdf). 
2/17: President's Day Holiday  Lecture 15: (4/07) Approximability, Averagecase hardness. Slides (pdf, ps). Draft of notes (tex, ps, pdf). 
(2/18: MIT Monday) Snowed Out  Lecture 16: (4/09) Average Case Complexity: Permanent, DNPCompleteness. Slides (pdf, ps). Draft of notes (tex, ps, pdf). 
Lecture 04: (2/19) Polynomial Hierarchy; Nonuniformity; Slides (pdf, ps). Notes (tex, ps, pdf).  Lecture 17: (4/14) A DNPcomplete problem. (Slodes  see lecture 16). 
Lecture 05: (2/24) Fortnow's Theorem; Randomization. Slides (pdf, ps). Notes (tex, ps, pdf).  Lecture 18: (4/16) Pseudorandomness. Constructions based on 1way functions and hard functions. Slides (pdf, ps). PS 4 Out 
Lecture 06:`(2/26) Some Randomized algorithms. BPP properties. Slides (pdf, ps). Draft of notes (tex, ps, pdf).  4/21: Patriots Day Holiday 
Lecture 07: (3/03) BPP in PH. Circuit Depth Lower Bound for Parity. Slides (pdf, ps). Draft of notes (tex, ps, pdf).  Lecture 19: (4/23) The NisanWigderson pseudorandom generator. (Lecturer: Prahladh Harsha.) Slides (pdf, ps). Draft of notes (tex, ps, pdf). 
Lecture 08: (3/05) Circuit lower bounds for Parity; Slides (pdf, ps).  Lecture 20: (4/28) Proof Complexity. (Lecturer: Eli BenSasson.) Draft of notes (tex, ps, pdf). 
Lecture 09: (3/10) Unique Satisfiability; Counting Classes. Slides (pdf, ps). Draft of notes (tex, ps, pdf).  Lecture 21: (4/30) Proof Complexity  II (Lecturer: Eli BenSasson.) 
Lecture 10: (3/12) Toda's theorem. Slides (not available). Draft of notes (tex, ps, pdf).  Lecture 22: (5/05) Quantum information and computation. 
Lecture 11: (3/17) Toda's Theorem (contd.) Slides (pdf, ps). Draft of notes (tex, ps, pdf).  Lecture 23: (5/07) BQP; Factoring in BQP. PS 4 Due. 
Lecture 12: (3/19) Interactive Proofs. ArthurMerlin Proofs. Slides (pdf, ps). Draft of notes (tex, ps, pdf).  Lecture 24: (5/12) Factoring in BQP (contd.) 
3/24: Spring Break  Lecture 25: (5/14) Conclusion; Review of advanced complexity! 
References