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