Chronological Order
- A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms. Boris A. Trakhtenbrot. 1984.
- The Minimum Equivalent DNF Problem and Shortest Implicants. Chris Umans. 1998.
- On the Complexity and Inapproximability of Shortest Implicant Problem. (.ps file) Chris Umans. 1999. Results also appear here.
- Hardness of Approximating Sigma2 Minimization Problems. (.ps file) Chris Umans. 1999.
- Circuit Minimization Problem. Valentine Kabanets, Jin-Yi Cai. 1999.
- When Worlds Collide: Derandomization, Lower Bounds, and Kolmogorov Complexity. (alt. pdf) Eric Allender. 2001.
- Power from Random Strings. Eric Allender, Harry Buhrman, Michal Koucký, Dieter van Melkebeek, Detlef Ronneburger. 2002.
- Minimizing DNF Formulas and AC0 Circuits Given a Truth Table. Eric Allender, Lisa Hellerstein, Paul McCabe, Michael Saks. 2005.
- Hardness of Approximate Two-level Logic Minimization and PAC Learning with Membership Queries. Vitaly Feldman. 2005.
- Nondeterministic Circuit Minimization Problem and Derandomizing Arthur-Merlin Games. (link?) Variyam Vinodchandran. 2005.
- The Complexity of Boolean Formula Minimization. David Buchfuhrer, Christopher Umans. 2008.
- The Pervasive Reach of Resource-Bounded Kolmogorov Complexity in Computational Complexity Theory. Eric Allender, Michal Koucky, Detlef Ronneburger, Sambuddha Roy. 2009.
- Improved Inapproximability Factors for Some Sigma2^p Minimization Problems. Kevin Dick, Chris Umans. 2009.
- Avoiding Simplicity is Complex Eric Allender, Holger Spakowski. 2010.
- Reductions to the set of random strings: the resource-bounded case. Eric Allender, Harry Burhman, Luke Friedman, Bruno Loff. 2012.
- Compression of Boolean Functions. Valentine Kabanets, Antonina Kolokolova. 2013.
- Mining Circuit Lower Bound Proofs for Meta-Algorithms. Ruiwen Chen, Valentine Kabanets, Antonina Kolokolova, Ronen Shaltiel, David Zuckerman. 2013.
- Zero Knowledge and Circuit Minimization. Eric Allender, Bireswar Das. 2014.
- The Minimum Oracle Circuit Size Problem. Eric Allender, Dhiraj Holden, Valentine Kabanets. 2014.
- On the (Non) NP-Hardness of Computing Circuit Complexity. Cody D. Murray, Richard Ryan Williams. 2014.
- Limits of Minimum Circuit Size Problem as Oracle. Shuichi Hirahara, Osamu Watanabe. 2015.
- On the NP-Completeness of the Minimum Circuit Size Problem John Hitchcock, A. Pavan. 2015.
- Algorithms from Natural Lower Bounds. Marco Carmosino, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova. 2016.
- Discrete Logarithm and Minimum Circuit Size. Michael Rudow. 2016.
- Complexity of Complexity (alt. pdf) Eric Allender. 2016.
- Conspiracies between Learning Algorithms, Circuit Lower Bounds and Pseudorandomness. Igor Carboni Oliveira, Rahul Santhanam. 2016.
- The Power of Natural Properties as Oracles. Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich. 2017.
- New Insights on the (Non)-Hardness of Circuit Minimization and Related Problems. Eric Allender, Shuichi Hirahara. 2017.
- On the Average-Case Complexity of MCSP and Its Variants Shuichi Hirahara, Rahul Santhanam. 2017.
- Agnostic Learning from Tolerant Natural Proofs. Marco Carmosino, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova. 2017.
- Minimum Circuit Size, Graph Isomorphism, and Related Problems. Eric Allender, Joshua A. Grochow, Dieter van Melkebeek, Cris Moore, Andrew Morgan. 2017.
- NP-hardness of Minimum Circuit Size Problem for OR-AND-MOD Circuits. Shuichi Hirahara, Igor Carboni Oliveira, Rahul Santhanam. 2018.
- Non-black-box Worst-case to Average-case Reductions within NP. Shuichi Hirahara. 2018.
- Hardness Magnification for Natural Problems. Igor Carboni Oliveira, Rahul Santhanam. 2018.