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

- Circuit Complexity and Communication Complexity (by Ran Raz). Project unassigned.
- Communication
lower bounds using dual polynomials (by Alexander Sherstov). Project unassigned.

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

- 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). Project unassigned.
- Arithmetization: A new method in structural complexity theory (by Laszlo Babai and Lance Fortnow). Project unassigned.
**The knowledge complexity of interactive proof systems**(by S. Goldwasser, S. Micali, and C Rackoff). Project unassigned.- Zero-Knowledge and Secure Computation (by O. Goldreich, S. Micali, and A. Wigderson). Project unassigned.
- A Complete Problem for Statistical Zero Knowledge (by Amit Sahai and Salil Vadhan). Project assigned. (Alex A. & Jessica Y.)
- The Shrinkage Exponent is 2 (by Johan Hastad). Project unassigned.
- Natural Proofs (by Alexander Razborov and Steven Rudich). Project unassigned.
- Constant-depth
circuits, Fourier transform and learnability (by Nati Linial,
Yishay Mansour and Noam Nisan). Project
assigned
(Huy N. & Vartika S.).

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

- Simple Analysis of graph tests for linearity and PCP (by Johan Hastad and Avi Wigderson). Project unassigned.
- The PCP Theorem by gap
amplification (by Irit Dinur). Project assigned (Sam M.
& Alessandro C.).

- New Lattice Based Cryptographic Constructions (by Oded Regev). Project unassigned.
- On Worst-Case to Average-Case Reductions for NP Problems (by Andrej Bogdanov and Luca Trevisan). Project unassigned.
- 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). Project unassigned.
- Derandomized Squaring of Graphs (by Eyal Rozenman and Salil Vadhan). Project assigned (Paul C. & Rishi G.).
- Hardness amplification within NP (by Ryan O'Donnell). Project assigned (Asilata B. & Alex C.).
- Hardcore
Distributions for Somewhat Hard
Problems (by Russell Impagliazzo). Project assigned (Mergen N.
& Colin Z.).

- Derandomizing Polynomial Identity Testing means Proving Circuit Lower Bounds (by Russell Impagliazzo and Valentine Kabanets). Project unassigned.
- Hardness vs. Randomness (by Noam Nisan and Avi Wigderson). Project assigned (David C. & Michael F.).
- Zero-Knowledge Proofs of Identity (by Amos Fiat, Uriel Feige, and Adi Shamir). Project assigned (Jeremy H. & Adam S.).
- 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.)