[1]   Manindra Agrawal, Eric Allender, Russell Impagliazzo, Toniann Pitassi, and Steven Rudich: Reducing the complexity of reductions. Comput. Complexity, 10(2):117–138, 2001. Preliminary version in STOC’97. [doi:10.1007/s00037-001-8191-1]

[2]   Miklós Ajtai: Σ₁¹-formulae on finite structures. Annals of Pure and Applied Logic, 24(1):1–48, 1983. [doi:10.1016/0168-0072(83)90038-6]

[3]   Eric Allender: When worlds collide: Derandomization, lower bounds, and Kolmogorov complexity. In 31th IARCS Conf. Found. of Software Tech. and Theoret. Comput. Sci. (FSTTCS’01), volume 2245 of LNCS, pp. 1–15. Springer, 2001. [doi:10.1007/3-540-45294-X_1]

[4]   Eric Allender: Personal communication, 2014.

[5]   Eric Allender, Harry Buhrman, Michal Koucký, Dieter van Melkebeek, and Detlef Ronneburger: Power from random strings. SIAM J. Comput., 35(6):1467–1493, 2006. Preliminary version in FOCS’02. [doi:10.1137/050628994]

[6]   Eric Allender and Bireswar Das: Zero knowledge and circuit minimization. Inform. and Comput., 2017. Preliminary versions in MFCS’14 and ECCC. [doi:10.1016/j.ic.2017.04.004]

[7]   Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi, and Michael Saks: Minimizing disjunctive normal form formulas and AC⁰ circuits given a truth table. SIAM J. Comput., 38(1):63–84, 2008. Preliminary version in CCC’06. [doi:10.1137/060664537]

[8]   Eric Allender, Dhiraj Holden, and Valentine Kabanets: The minimum oracle circuit size problem. Comput. Complexity, 26(2):469–496, 2017. Preliminary version in STACS’15. [doi:10.1007/s00037-016-0124-0]

[9]   Sanjeev Arora and Boaz Barak: Computational Complexity: A Modern Approach. Cambridge Univ. Press, 2009.

[10]   Harry Buhrman, Lance Fortnow, and Thomas Thierauf: Nonrelativizing separations. In Proc. 13th IEEE Conf. on Computational Complexity (CCC’98), pp. 8–12. IEEE Comp. Soc. Press, 1998. [doi:10.1109/CCC.1998.694585]

[11]   Sebastian Czort: The complexity of minimizing disjunctive normal form formulas, 1999. Master’s Thesis, University of Aarhus.

[12]   Vitaly Feldman: Hardness of approximate two-level logic minimization and PAC learning with membership queries. J. Comput. System Sci., 75(1):13–26, 2009. Preliminary versions in STOC’06 and ECCC. [doi:10.1016/j.jcss.2008.07.007]

[13]   Oded Goldreich, Shafi Goldwasser, and Silvio Micali: How to construct random functions. J. ACM, 33(4):792–807, 1986. Preliminary version in FOCS’84. [doi:10.1145/6490.6503]

[14]   Oded Goldreich, Silvio Micali, and Avi Wigderson: Proofs that yield nothing but their validity for all languages in NP have zero-knowledge proof systems. J. ACM, 38(3):691–729, 1991. Preliminary version in FOCS’86. [doi:10.1145/116825.116852]

[15]   Johan Håstad: Almost optimal lower bounds for small depth circuits. In Proc. 18th STOC, pp. 6–20. ACM Press, 1986. [doi:10.1145/12130.12132]

[16]   Shuichi Hirahara and Osamu Watanabe: Limits of minimum circuit size problem as oracle. In Proc. 31st IEEE Conf. on Computational Complexity (CCC’16), volume 50, pp. 18:1–18:20. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. Available at ECCC. [doi:10.4230/LIPIcs.CCC.2016.18]

[17]   John M. Hitchcock and Aduri Pavan: On the NP-completeness of the minimum circuit size problem. In 35th IARCS Conf. Found. of Software Tech. and Theoret. Comput. Sci. (FSTTCS’15), volume 45 of LIPIcs, pp. 236–245, 2015. [doi:10.4230/LIPIcs.FSTTCS.2015.236]

[18]   Russell Impagliazzo, Valentine Kabanets, and Avi Wigderson: In search of an easy witness: exponential time vs. probabilistic polynomial time. J. Comput. System Sci., 65(4):672–694, 2002. Preliminary version in CCC’01. [doi:10.1016/S0022-0000(02)00024-7]

[19]   Russell Impagliazzo and Avi Wigderson: P = BPP if E requires exponential circuits: Derandomizing the XOR lemma. In Proc. 29th STOC, pp. 220–229. ACM Press, 1997. [doi:10.1145/258533.258590]

[20]   Valentine Kabanets and Jin-yi Cai: Circuit minimization problem. In Proc. 32nd STOC, pp. 73–79. ACM Press, 2000. [doi:10.1145/335305.335314]

[21]   Cody D. Murray and R. Ryan Williams: On the (non) NP-hardness of computing circuit complexity. In Proc. 30th IEEE Conf. on Computational Complexity (CCC’15), volume 33 of LIPIcs, pp. 365–380. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2015. [doi:10.4230/LIPIcs.CCC.2015.365]

[22]   Christos H. Papadimitriou and Mihalis Yannakakis: A note on succinct representations of graphs. Inf. Control, 71(3):181–185, 1986. [doi:10.1016/S0019-9958(86)80009-2]

[23]   Sven Skyum and Leslie G. Valiant: A complexity theory based on Boolean algebra. J. ACM, 32(2):484–502, 1985. Preliminary version in SFCS’81. [doi:10.1145/3149.3158]

[24]   N. Variyam Vinodchandran: Nondeterministic circuit minimization problem and derandomizing Arthur-Merlin games. Int. J. Found. Comput. Sci., 16(6):1297–1308, 2005. [doi:10.1142/S0129054105003819]

[25]   Heribert Vollmer: Introduction to Circuit Complexity: A Uniform Approach. Texts in Theoretical Computer Science. An EATCS Series. Springer, 1999. [doi:10.1007/978-3-662-03927-4]

[26]   R. Ryan Williams: Natural proofs versus derandomization. SIAM J. Comput., 45(2):497–529, 2016. Preliminary version in STOC’13. [doi:10.1137/130938219, arXiv:1212.1891]

[27]   Stanislav Žák: A Turing machine time hierarchy. Theoret. Comput. Sci., 26(3):327–333, 1983. [doi:10.1016/0304-3975(83)90015-4]