MIT 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 Here
Bulletin Board
 
1. Sign up for scribing. See 
    scribes.txt for availability.

 

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

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

References