Harvard University homepage
HARVARD.EDU

Madhu Sudan: 6.841/18.405J: Advanced Complexity Theory

Course Staff

Lecturer: Madhu Sudan

NE 43-307
first name at mit.edu

TA: Prahladh Harsha

NE43-338
first name at theory.lcs.mit.edu
Office hours: Mondays 3-5pm
+ 3-5pm on day before pset due date.

General Information

Prerequisite: 6.840

Time: MW 1-2:30

Location: 2-105

3-0-9 H Level Credit

http://theory.lcs.mit.edu/~madhu/ST03

Course announcement

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

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 2002 give further details on the material covered.

Instructor: Madhu Sudan

Bulletin Board

1. Sign up for scribing. See scribes.txt for availability.

Problem Sets

Schedule of Lectures

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

References