Harvard University homepage
HARVARD.EDU

Madhu Sudan: 6.841/18.405J: Advanced Complexity Theory

Course number: 6.841 J/18.405J
Prereq: 6.840
Time: MW 11:00-12:30pm
Location: 26-322
3-0-9 H-Level Grad Credit
Lecturer: Madhu Sudan
TA: Swastik Kopparty
Homepage: http://theory.csail.mit.edu/~madhu/ST07

Bulletin Board

Grading Policy

Grades will be based on a combination of the following ingredients

  1. Three Problem Sets.
  2. A course project (instructions to be posted shortly).
  3. Class Participation (especially towards the second half of the term).
  4. Additionally, you must scribe at least one lecture.
List of projects is now available. Please start scanning the topics and make sure you have chosen one before spring break.

Potential Project Topics for Advanced Complexity Theory (MIT 6.841/18.405):

  1. A Switching Lemma Primer (by Paul Beame). Project unassigned.
  2. Circuit Complexity and Communication Complexity (by Ran Raz). (Tasos and K. Onak).
  3. Time-Space Lower Bounds for Satisfiability. (by L. Fortnow, R. Lipton, D. van Melkebeek, and A. Viglas). (Jaime and Mayank).
  4. A Generic Time Hierarchy for Semantic Models With One Bit of Advice (by Dieter van Melkebeek and Konstantin Pervyshev). Project Unassigned.
  5. The Complexity of Computing the Permanent. (by Leslie Valiant). (Tim and Alex).
  6. Arithmetization: A new method in structural complexity theory (by Laszlo Babai and Lance Fortnow). (Nadia and Cathy).
  7. The knowledge complexity of interactive proof systems (by S. Goldwasser, S. Micali, and C Rackoff). Project assigned (Adam+Alan).
  8. Zero-Knowledge and Secure Computation (by O. Goldreich, S. Micali, and A. Wigderson).  Project assigned (Eitan+Igor).
  9. A Complete Problem for Statistical Zero Knowledge (by Amit Sahai and Salil Vadhan). Project assigned (John+Travis).
  10. The Shrinkage Exponent is 2 (by Johan Hastad). Project unassigned.
  11. Simple Analysis of graph tests for linearity and PCP (by Johan Hastad and Avi Wigderson). (Jelani and Amanda).
  12. The PCP Theorem by gap amplification (by Irit Dinur). Project assigned (Oren+Petar).
  13. New Lattice Based Cryptographic Constructions (by Oded Regev). Project assigned (Ning+Alex).
  14. On Worst-Case to Average-Case Reductions for NP Problems (by Andrej Bogdanov and Luca Trevisan). Favonius and Nate.
  15. On the random-self-reducibility of complete sets (Joan Feigenbaum and Lance Fortnow). Project unassigned.
  16. Quantum circuit complexity (by Andrew Yao). Project unassigned.
  17. Exponential Separation of Quantum and Classical One-Way Communication Complexity (by Z. Bar-Yossef, T.S. Jayram,  and I. Kerenidis). (Jose and Suho).
  18. Derandomized Squaring of Graphs (by Eyal Rozenman and Salil Vadhan). Project Assigned (Shubhangi and Anand).
  19. Hardness amplification within NP (by Ryan O’Donnell). Project Assigned (Punya and David).
  20. Hardcore Distributions for Somewhat Hard Problems (by Russell Impagliazzo). Project unassigned.
  21. Derandomizing Polynomial Identity Testing means Proving Circuit Lower Bounds (by Russell Impagliazzo and Valentine Kabanets). (Shivani and Salman).
Course announcement

Course announcement: Advanced Complexity Theory (6.841/18.405) – Spring 2007

Prereq: 6.840.
Time: MW 11-12:30
Location: 26-322
3-0-9 H-Level Grad Credit
Homepage: http://theory.csail.mit.edu/~madhu/ST07/ 

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. Non-uniform models of computation and lower bounds.
  4. Interaction, proof, and knowledge.
  5. Probabilistically checkable proofs and Inapproximability.
  6. Quantum computation.

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

Instructor: Madhu Sudan

Tentative list of Topics:

  • Lecture 01 (02/07): Introduction. Review of Complexity. Notes. Scribe notes (lect01.tex, lect01.pdf).
  • Lecture 02 (02/12): Diagonalization and Relativization. Ladner’s theorem. Notes. Scribe notes (lect02.tex, lect02.pdf).
  • Lecture 03 (02/14): Non-uniform complexity. Neciporuk’s Lower Bound for Formula Size. Notes. Scribe notes (lect03.tex, lect03.pdf).
  • Monday 02/19: Presidents Day Holiday.
  • Lecture 04 (02/20): MIT Virtual Monday! Barrington’s theorem. Notes. Scribe notes (lect04.tex, lect04.pdf).
  • Lecture 05 (02/21): Parity is not in AC0 (Furst-Saxe-Sipser). Notes. Scribe notes (lect05.tex, lect05.pdf).
  • Lecture 06 (02/26): Parity is not in AC0 (Razborov-Smolensky). Notes. Scribe notes (lect06.tex, lect06.pdf).
  • Lecture 07 (02/28): Communication Complexity and Circuit lower bounds. Notes. Scribe notes (lect07.tex, lect07.pdf).
  • Lecture 08 (03/05): Alternation: Time vs. Space. Fortnow’s theorem. Notes. Scribe notes (lect08.tex, lect08.pdf).
  • Lecture 09 (03/07): Debates, Alternation, Polynomial Hierarchy, Karp-Lipton theorem. Notes. Scribe notes (lect09.tex, lect09.pdf).
  • Lecture 10 (03/12): Randomness and computing. Algorithms, Models, Classes, Promise Problems. Notes. Scribe notes (lect10.tex, lect10.pdf).
  • Lecture 11 (03/14): Properties of BPP: Amplification, Low circuit complexity, Containment in PH. Notes. Scribe notes (lect11.tex, lect11.pdf).
  • Lecture 12 (03/19): Complexity of Unique Satisfiability. Counting Problems. Notes. Scribes notes (lect12.tex, lect12.pdf).
  • Lecture 13 (03/21): Toda’s theorem: Alternation reduces to counting. Notes. Scribe notes (lect13.tex, lect13.pdf).
  • 03/26 – 03/30: Spring Break!
  • Lecture 14 (04/02): Interactive Proofs. AM, IP. Notes. Scribe notes (lect14.tex, lect14.pdf).
  • Lecture 15 (04/04): IP vs. PSPACE. #P in IP. Notes. Scribe notes (lect15.tex, lect15.pdf).
  • Lecture 16 (04/09): Straightline program with polynomials. IP=PSPACE. (No notes.) Scribe notes (lect16.tex, lect16.pdf).
  • Lecture 17 (04/11): Knowledge, Statistical and Computational. Notes. Scribe notes (lect17.tex, lect17.pdf).
  • Monday 04/16: Patriots Day Holiday.
  • Lecture 18 (04/18): Probabilistically checkable proofs. Statement of the PCP theorem. Approximation and Inapproximability. Scribe notes (lect18.tex, lect18.pdf).
  • Lecture 19 (04/23): PCP – An exponentially long, O(1)-query, PCP for satisfiability. Notes. Scribe notes (lect19.tex, lect19.pdf).
  • Lecture 20 (04/25): PCP – Dinur’s proof of the PCP Theorem (most of it). Notes. Scribe notes (lect20.tex, lect20.pdf).
  • Lecture 21 (04/30): Average case complexity: Definitions. Notes. Scribe notes (lect21.tex, lect21.pdf).
  • Lecture 22 (05/02): Average case complexity: A DNP complete problem. Notes. Scribe notes (lect22.tex, lect22.pdf).
  • Lecture 23 (05/07): Average case complexity – III. problem. Scribe notes (lect23.tex, lect23.pdf).
  • Lecture 24 (05/09): CANCELLED Due to Project Presentations
  • Wednesday (05/09): 9am-12:30pm: Project Presentations in G531 (Signup info here).
  • Thursday (05/10): 9am-12:30pm: Project Presentations in G631 (Signup info here)
  • Lecture 25 (05/14): Quantum computing.
  • Lecture 26 (05/16): Conclusions.

References

Scribes