MIT 6.841/18.405J Advanced Complexity Theory (Spring 2005)


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