PROJECT TOPICS
- On the (im)possibility of obfuscating programs, by Barak, Goldreich, Impagliazzo, Rudich, Sahai, Vadhan, and Yang
- Exponential Lower Bounds for Polytopes in Combinatorial Optimization, by Fiorini, Massar, Pokutta, Tiwary, and de Wolf
- How to Compress Interactive Communication, by Barak, Braverman, Chen, and Rao
- Deterministic Communication vs. Partition Number, by Goos, Pitassi, and Watson
- Hardness amplification within NP, by O'Donnell
- On the complexity of the parity argument and other inefficient proofs of existence, by Papadimitriou
- Bipartite Perfect Matching is in Quasi-NC, by Fenner, Gurjar, and Thierauf
- Hardness vs randomness, by Nisan and Wigderson
- Nonuniform ACC Circuit Lower Bounds, by Williams
- Cryptography in NC0, by Applebaum, Ishai, Kushilevitz
- Which Problems Have Strongly Exponential Complexity?, by Impagliazzo, Paturi, and Zane
- A complete problem for statistical zero knowledge, by Sahai and Vadhan
- Pseudorandom generators for space-bounded computation, by Nisan
- Pseudorandom Generators without the XOR Lemma, by Sudan, Trevisan, and Vadhan
- Algebrization: A New Barrier in Complexity Theory, by Aaronson and Wigderson