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

- A
Switching Lemma Primer (by Paul Beame). Project unassigned.

- Circuit
Complexity and Communication Complexity (by Ran Raz). (Tasos and K. Onak).
- Time-Space
Lower Bounds for Satisfiability. (by L. Fortnow, R.
Lipton, D. van Melkebeek, and A. Viglas). (Jaime and Mayank).

- A
Generic Time Hierarchy for Semantic Models With One Bit of Advice
(by Dieter van Melkebeek and Konstantin Pervyshev). Project Unassigned.

- The
Complexity of Computing the Permanent. (by Leslie Valiant). (Tim and Alex).

- Arithmetization:
A new
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
(Adam+Alan).

- Zero-Knowledge
and Secure Computation (by O. Goldreich, S. Micali, and A.
Wigderson). Project
assigned (Eitan+Igor).

- A
Complete Problem for Statistical Zero Knowledge (by Amit Sahai and
Salil Vadhan). Project assigned
(John+Travis).

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

- New
Lattice Based Cryptographic Constructions (by Oded Regev). Project assigned (Ning+Alex).

- On
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
unassigned.

- Quantum
circuit complexity (by Andrew Yao). Project unassigned.

- Exponential
Separation of Quantum and Classical One-Way Communication Complexity
(by
Z. Bar-Yossef, T.S. Jayram, and I. Kerenidis). (Jose and Suho).

- Derandomized
Squaring of
Graphs (by Eyal Rozenman and Salil Vadhan). Project Assigned (Shubhangi and Anand).
- Hardness
amplification within NP (by Ryan O'Donnell). Project Assigned (Punya and David).

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