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