Advanced Complexity Theory
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
3-0-9 H Level Credit
Bulletin
Board
Last set of comments due Tuesday.
Problem
Sets
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