Prereq: 6.840J/18.404J
Time: MW 11-12:30
Location: 26-322
3-0-9 H-Level Grad Credit
Homepage: http://courses.csail.mit.edu/6.841

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.

A tentative list of topics is available from the course website (http://courses.csail.mit.edu/6.841).

Lecture notes for this course from previous semesters give further details on the material covered. These may be found at
http://people.csail.mit.edu/madhu/ST02,  http://people.csail.mit.edu/madhu/ST03, http://people.csail.mit.edu/madhu/ST05, and http://people.csail.mit.edu/madhu/ST07.

Instructor: Madhu Sudan   TA: Brendan Juba

Grades will be based on a combination of the following ingredient

1. 2-4 Problem Sets.
2. A course project (instructions to be posted shortly).
3. Class Participation (biased towards the second half of the term).
4. Additionally, you must scribe at least one lecture.

Instructions for working on and turning in problem sets

Problem Sets: PS1, PS2, PS3.

1. Collaboration is allowed and encouraged. You are allowed to read any material, but it will be counterproductive to your interests to run to Google to search for solutions to the problems. Better to think on your own, and seek references only for hints or to improve your understanding of the material.
2. No matter how you solve the problems, you must write your solutions on your own and you must cite all sources (collaborators and other references).
3. Turn in your problem sets electronically by email to bjuba at mit dot edu. You can write your solutions in any format you choose, but submit as pdf or plain text.
4. Deadlines are for 10pm on the due date.

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

1. A Switching Lemma Primer (by Paul Beame). Project unassigned.
2. Circuit Complexity and Communication Complexity (by Ran Raz). Project unassigned.
3. Communication lower bounds using dual polynomials (by Alexander Sherstov). Project unassigned.
4. Alternation-Trading Proofs, Linear Programming, and Lower Bounds (by Ryan Williams); or A Survey of Lower Bounds for Satisfiability and Related Problems (by Dieter van Melkebeek). Project assigned (Rotem O. & Jean Y.)
5. A Generic Time Hierarchy for Semantic Models With One Bit of Advice (by Dieter van Melkebeek and Konstantin Pervyshev). Project Unassigned.
6. The Complexity of Computing the Permanent. (by Leslie Valiant). Project unassigned.
7. Arithmetization: A new method in structural complexity theory (by Laszlo Babai and Lance Fortnow). Project unassigned.
8. The knowledge complexity of interactive proof systems (by S. Goldwasser, S. Micali, and C Rackoff). Project unassigned.
9. Zero-Knowledge and Secure Computation (by O. Goldreich, S. Micali, and A. Wigderson).  Project unassigned.
10. A Complete Problem for Statistical Zero Knowledge (by Amit Sahai and Salil Vadhan). Project assigned. (Alex A. & Jessica Y.)
11. The Shrinkage Exponent is 2 (by Johan Hastad). Project unassigned.
12. Natural Proofs (by Alexander Razborov and Steven Rudich). Project unassigned.
13. Constant-depth circuits, Fourier transform and learnability (by Nati Linial, Yishay Mansour and Noam Nisan). Project assigned (Huy N. & Vartika S.).
14. (Polylogarithmic  independence can fool  DNF formulas (by Louay Bazzi) OR A simple proof of Bazzi’s theorem (by Alexander Razborov)) AND (Poly-logarithmic independence fools AC0 circuits (by Mark Braverman)). Project unassigned.
15. Simple Analysis of graph tests for linearity and PCP (by Johan Hastad and Avi Wigderson). Project unassigned.
16. The PCP Theorem by gap amplification (by Irit Dinur). Project assigned (Sam M. & Alessandro C.).
17. New Lattice Based Cryptographic Constructions (by Oded Regev). Project unassigned.
18. On Worst-Case to Average-Case Reductions for NP Problems (by Andrej Bogdanov and Luca Trevisan). Project unassigned.
19. On the random-self-reducibility of complete sets (Joan Feigenbaum and Lance Fortnow). Project unassigned.
20. Quantum circuit complexity (by Andrew Yao). Project unassigned.
21. Exponential Separation of Quantum and Classical One-Way Communication Complexity (by Z. Bar-Yossef, T.S. Jayram,  and I. Kerenidis). Project unassigned.
22. Derandomized Squaring of Graphs (by Eyal Rozenman and Salil Vadhan). Project assigned (Paul C. & Rishi G.).
23. Hardness amplification within NP (by Ryan O’Donnell). Project assigned (Asilata B. & Alex C.).
24. Hardcore Distributions for Somewhat Hard Problems (by Russell Impagliazzo). Project assigned (Mergen N. & Colin Z.).
25. Derandomizing Polynomial Identity Testing means Proving Circuit Lower Bounds (by Russell Impagliazzo and Valentine Kabanets). Project unassigned.
26. Hardness vs. Randomness (by Noam Nisan and Avi Wigderson). Project assigned (David C. & Michael F.).
27. Zero-Knowledge Proofs of Identity (by Amos Fiat, Uriel Feige, and Adi Shamir). Project assigned (Jeremy H. & Adam S.).
28. Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs? (by Subhash Khot, Guy Kindler, Elchanan Mossel, Ryan O’Donnell). Project assigned (Debmalya P. & Yang C.)