Harvard University homepage
HARVARD.EDU

Madhu Sudan: 6.841/18.405J: Advanced Complexity Theory

Course Staff

Lecturer: Madhu Sudan 32G-640 first name at mit.edu

A: Sergey Yekhanin 32G-614 last name at theory.lcs.mit.eduOffice 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

Course announcement

Prereq: 6.840.
Time: MW 1-2:30
Location: 32-124
3-0-9 H-Level Grad Credit
Homepage: http://theory.lcs.mit.edu/~madhu/ST05/ 

Advanced Complexity Theory

This course is a follow-up to Introduction to the theory of computation (6.840). It covers advanced topics in computational complexity, leading up to the state-of-the-art in the field. Principal topics include:

  1. Review of time and space complexity.
  2. Non-determinism and alternation.
  3. Randomized computation and derandomization.
  4. Non-uniform models and lower bounds.
  5. Interaction, proof, and knowledge.
  6. Quantum computation.

Lecture notes for this course from Spring 2003 give further details on the material covered. These may be found at
http://theory.lcs.mit.edu/~madhu/ST03/

Instructor: Madhu Sudan

Bulletin Board

Last set of comments due Tuesday.

Problem Sets

Tentative schedule of lectures

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

References