PROJECT TOPICS
Each link goes to the official (journal or conference) version, which is available in full text through the UIUC library.
- Delegating Computation: Interactive Proofs for Muggles, by Goldwasser, Kalai, and Rothblum (J. ACM 2015)
- Pseudorandom generators for space-bounded computation, by Nisan (Combinatorica 1992)
- Lower bounds for non-commutative computation, by Nisan (STOC 1991), and Deterministic polynomial identity testing in non-commutative models, by Raz and Shpilka (Computational Complexity 2005)
- Separations in Query Complexity Based on Pointer Functions, by Ambainis, Balodis, Belovs, Lee, Santha, and Smotrovs (J. ACM 2017)
- Simulating Time with Square-Root Space, by Williams (STOC 2025), and Tree Evaluation is in Space O(log n · log log n), by Cook and Mertz (SIAM J. Comput. 2025)
- Matching is as easy as matrix inversion, by Mulmuley, Vazirani, and Vazirani (Combinatorica 1987), and Bipartite Perfect Matching is in Quasi-NC, by Fenner, Gurjar, and Thierauf (SIAM J. Comput. 2021)
- Algebrization: A New Barrier in Complexity Theory, by Aaronson and Wigderson (ACM Trans. Comput. Theory 2009)
- Circuit Lower Bounds for Merlin–Arthur Classes, by Santhanam (SIAM J. Comput. 2009)
- A complete problem for statistical zero knowledge, by Sahai and Vadhan (J. ACM 2003)
- Infeasibility of instance compression and succinct PCPs for NP, by Fortnow and Santhanam (J. Comput. Syst. Sci. 2011)
- Deterministic Communication vs. Partition Number, by Göös, Pitassi, and Watson (SIAM J. Comput. 2018)
- Amplifying Lower Bounds by Means of Self-Reducibility, by Allender and Koucký (J. ACM 2010)
- Edit Distance Cannot Be Computed in Strongly Subquadratic Time (Unless SETH is False), by Backurs and Indyk (SIAM J. Comput. 2018)
- Short proofs are narrow—resolution made simple, by Ben-Sasson and Wigderson (J. ACM 2001)
- PP Is Closed under Intersection, by Beigel, Reingold, and Spielman (J. Comput. Syst. Sci. 1995)
- Circuit minimization problem, by Kabanets and Cai (STOC 2000), and On the (Non) NP-Hardness of Computing Circuit Complexity, by Murray and Williams (Theory of Computing 2017)
- On the (im)possibility of obfuscating programs, by Barak, Goldreich, Impagliazzo, Rudich, Sahai, Vadhan, and Yang (J. ACM 2012)
- Exponential Lower Bounds for Polytopes in Combinatorial Optimization, by Fiorini, Massar, Pokutta, Tiwary, and de Wolf (J. ACM 2015)
- On the complexity of the parity argument and other inefficient proofs of existence, by Papadimitriou (J. Comput. Syst. Sci. 1994)
- Cryptography in NC0, by Applebaum, Ishai, and Kushilevitz (SIAM J. Comput. 2006)
- Computing with a full memory: catalytic space, by Buhrman, Cleve, Koucký, Loff, and Speelman (STOC 2014), and Computing Algebraic Formulas Using a Constant Number of Registers, by Ben-Or and Cleve (SIAM J. Comput. 1992)
- On Data Structures and Asymmetric Communication Complexity, by Miltersen, Nisan, Safra, and Wigderson (J. Comput. Syst. Sci. 1998)