Project Topics for Advanced Complexity Theory (MIT 6.841/18.405; Spring
Switching Lemma Primer (by Paul Beame). Project unassigned.
Complexity and Communication Complexity (by Ran Raz). Project unassigned.
lower bounds using dual polynomials (by Alexander Sherstov). Project unassigned.
Proofs, Linear Programming, and Lower Bounds (by Ryan Williams); or
Survey of Lower Bounds for Satisfiability and Related Problems (by
Dieter van Melkebeek). Project assigned (Rotem O. & Jean Y.)
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). Project unassigned.
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.
and Secure Computation (by O. Goldreich, S. Micali, and 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.
Proofs (by Alexander Razborov and Steven Rudich). Project unassigned.
circuits, Fourier transform and learnability (by Nati Linial,
Yishay Mansour and Noam Nisan). Project
(Huy N. & Vartika S.).
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.).
Lattice Based Cryptographic Constructions (by Oded Regev). Project unassigned.
Worst-Case to Average-Case Reductions for NP Problems (by Andrej
Bogdanov and Luca Trevisan). Project
- 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). Project unassigned.
Graphs (by Eyal Rozenman and Salil Vadhan). Project assigned (Paul C.
& Rishi G.).
amplification within NP (by Ryan O'Donnell). Project assigned (Asilata B. & Alex C.).
Distributions for Somewhat Hard
Problems (by Russell Impagliazzo). Project assigned (Mergen N.
& Colin Z.).
Polynomial Identity Testing means Proving Circuit Lower Bounds (by
Russell Impagliazzo and Valentine Kabanets). Project unassigned.
vs. Randomness (by Noam Nisan and Avi Wigderson). Project assigned (David C.
& Michael F.).
Proofs of Identity (by Amos Fiat, Uriel Feige, and Adi Shamir). Project assigned (Jeremy H.
& Adam S.).
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.)