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.)
    

Back to Course Homepage