Course Staff Lecturer: Madhu Sudan       32G-640       first name at mit.edu  TA: Sergey Yekhanin         32G-614         last name at theory.lcs.mit.edu         Office hours: TBA

General Information   Prerequisite: 6.840 Time: MW 1-2:30 Location: 32-124 3-0-9 H Level Credit http://theory.lcs.mit.edu/~madhu/ST05 Course Announcement Here

Bulletin Board   Last set of comments due Tuesday.

Problem Sets   PS1 (tex, pdf, ps). PS2 (tex, pdf, ps). PS3 (tex, pdf, ps).

Tentative schedule of lectures:
 

Lecture 01: (02/02) Introduction, Review of Complexity; Slides (pdf, ps). Notes (tex, ps, pdf).	Lecture 14: (03/28) Toda's Theorem.  Slides (pdf, ps). Notes (tex, ps, pdf).
Lecture 02: (02/07) Diagonalization and Relativization; Ladner's Theorem; Slides (pdf, ps). Notes (tex, ps, pdf).	Lecture 15: (03/30) Interactive Proofs, AM, IP. Slides (pdf, ps). Notes (tex, ps, pdf).
Lecture 03: (02/09) Non-uniform complexity; Neciporuk's lower bound for formula size; Slides (pdf, ps). Notes (tex,ps, pdf).	Lecture 16: (04/04) IP vs. PSPACE. #P in IP. Slides (pdf, ps). Notes (tex, ps, pdf).
Lecture 04: (02/14) Barrington's Theorem; Slides (pdf, ps). Notes (tex, ps, pdf).	Lecture 17: (04/06) Straightline Progams with Polynomials. IP=PSPACE. Slides (pdf, ps). Notes (tex, ps, pdf).
Lecture 05: (2/16) Furst-Saxe-Sipser: Parity is not in AC0. Slides (pdf, ps). Notes (tex, ps, pdf).	Lecture 18: (04/11) Probabilistically checkable Proofs. A weak PCP theorem. Slides (pdf, ps). Notes (tex, ps, pdf).
02/21: Presidents Day Holiday	Lecture 19: (04/13) PCPs contd. Slides (pdf, ps). Notes (tex, ps, pdf).
Lecture 06: (02/22) MIT Monday. Razborov-Smolensky proof that Parity is not in AC0. Slides (pdf, ps). Notes (tex, ps, pdf).	04/18: Patriots Day Holiday.
Lecture 07: (02/23) Smolensky's proof (contd.). Communication complexity. Slides (pdf, ps). Notes (tex, ps, pdf).	Lecture 20: (04/20) PCPs and Approximation. Dinur's proof of the PCP Theorem. Slides (pdf, ps). Notes (tex, ps, pdf).
Lecture 08: (02/28) Alternation, Time, vs. Space. Slides (pdf, ps). Notes (tex, ps, pdf).	Lecture 21: (04/25) Dinur's proof of the PCP theorem (contd.). Slides (pdf, ps). Notes (tex, ps, pdf).
Lecture 09: (03/02) Karp-Lipton Theorem. Fortnow's Theorem. Slides (pdf, ps). Notes (tex, ps, pdf).	Lecture 22: (04/27) Pseudorandomness; Derandomization of BPP. Slides (pdf, ps). Notes (tex, ps, pdf).
Lecture 10: (03/07) Randomness and Computing. Algorithms. Models. Classes. Promise problems. Slides (pdf, ps). Notes (tex, ps, pdf).	Lecture 23: (05/02) The Nisan-Wigderson pseudorandom generator. The Impagliazzo-Wigderson theorem. Slides (pdf, ps). Notes (tex, ps, pdf).
Lecture 11: (03/09) Properties of BPP: Amplification, Low circuit complexity, Containment in PH. Slides (pdf, ps). Notes (tex, ps, pdf).	Lecture 24: (05/04) Trevisan's Extractor. Average Case Complexity. Slides (pdf, ps). Notes (tex, ps, pdf).
Lecture 12: (03/14) BPP is in PH. Complexity of Unique Satisfiability. Slides (pdf, ps). Notes (tex, ps, pdf).	Lecture 25: (05/09) Average Case Complexity. Quantum Computation. Slides (pdf, ps). Notes (tex, ps, pdf).
Lecture 13 (03/16) Counting Problems, Permanent, Worst-case vs. Average-case. Slides (pdf, ps). Notes (tex, ps, pdf).	Lecture 26: (05/11)) Shor's factoring (Bird's eye view). Slides (pdf, ps). Notes (tex, ps, pdf).
03/21-03/25: Spring Break	End of classes.

References

• Dan Spielman's Lecture Notes from Spring 2001 http://www-math.mit.edu/~spielman/AdvComplexity/2001.
• Lecture Notes from Spring 2002 http://theory.lcs.mit.edu/~madhu/ST02.
• Christos Papadimitriou's text: Computational Complexity.
• Michael Sipser's text: Introduction to the Theory of Computation (for initial lectures only).