PROJECT TOPICS
- Delegating Computation: Interactive Proofs for Muggles, by Goldwasser, Kalai, and Rothblum
- Which Problems Have Strongly Exponential Complexity?, by Impagliazzo, Paturi, and Zane
- Pseudorandom Generators without the XOR Lemma, by Sudan, Trevisan, and Vadhan
- Polylogarithmic independence fools AC0 circuits, by Braverman
- Approaching the Chasm at Depth Four, by Gupta, Kayal, Kamath, and Saptharishi
- How to Compress Interactive Communication, by Barak, Braverman, Chen, and Rao
- Parallel Repetition From Fortification, by Moshkovitz
- Algebrization: A New Barrier in Complexity Theory, by Aaronson and Wigderson
- Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds, by Kabanets and Impagliazzo
- Communication is Bounded by Root of Rank, by Lovett
- A complete problem for statistical zero knowledge, by Sahai and Vadhan
- Cryptography in NC0, by Applebaum, Ishai, Kushilevitz
- Deterministic Communication vs. Partition Number, by Goos, Pitassi, and Watson
- Exponential Lower Bounds for Polytopes in Combinatorial Optimization, by Fiorini, Massar, Pokutta, Tiwary, and de Wolf
- Hardness amplification within NP, by O'Donnell
- Nonuniform ACC Circuit Lower Bounds, by Williams
- Pseudorandom generators for space-bounded computation, by Nisan
- On the (im)possibility of obfuscating programs, by Barak, Goldreich, Impagliazzo, Rudich, Sahai, Vadhan, and Yang