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