[1]   Scott Aaronson: PNP. In Open Problems in Mathematics, pp. 1–122. Springer, 2016. [ECCC:TR17-004]

[2]   Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, and Avi Wigderson: Pseudorandom generators in propositional proof complexity. SIAM J. Comput., 34(1):67–88, 2004. [doi:10.1137/S0097539701389944, ECCC:TR00-023]

[3]   Eric Allender: When worlds collide: Derandomization, lower bounds, and Kolmogorov complexity. In Proc. 21st Found. Softw. Techn. Theoret. Comp. Sci. Conf. (FSTTCS’01), pp. 1–15. Springer, 2001. [doi:10.1007/3-540-45294-X_1]

[4]   Eric Allender: The new complexity landscape around circuit minimization. In Proc. 14th Internat. Conf. Lang. Autom. Theory and Appl. (LATA’20), pp. 3–16. Springer, 2020. [doi:10.1007/978-3-030-40608-0_1, ECCC:TR20-078]

[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. [doi:10.1137/050628994]

[6]   Eric Allender and Michal Koucký: Amplifying lower bounds by means of self-reducibility. J. ACM, 57(3):14:1–36, 2010. [doi:10.1145/1706591.1706594]

[7]   Andrej Bogdanov: Small-bias requires large formulas. In Proc. 45th Internat. Colloq. on Automata, Languages, and Programming (ICALP’18), pp. 22:1–12. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018. [doi:10.4230/LIPIcs.ICALP.2018.22, ECCC:TR18-139]

[8]   Ravi B. Boppana and Michael Sipser: The complexity of finite functions. In Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity, pp. 757–804. Elsevier, 1990. [doi:10.1016/B978-0-444-88071-0.50019-9]

[9]   Nader H. Bshouty, Richard Cleve, Ricard Gavaldà, Sampath Kannan, and Christino Tamon: Oracles and queries that are sufficient for exact learning. J. Comput. System Sci., 52(3):421–433, 1996. [doi:10.1006/jcss.1996.0032]

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

[11]   Jin-yi Cai: S₂^p ⊆ ZPP^NP. J. Comput. System Sci., 73(1):25–35, 2007. [doi:10.1016/j.jcss.2003.07.015]

[12]   Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, and Antonina Kolokolova: Learning algorithms from natural proofs. In Proc. 31st Comput. Complexity Conf. (CCC’16), pp. 10:1–24. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2016. [doi:10.4230/LIPIcs.CCC.2016.10]

[13]   Marco L. Carmosino, Russell Impagliazzo, Shachar Lovett, and Ivan Mihajlin: Hardness amplification for non-commutative arithmetic circuits. In Proc. 33rd Comput. Complexity Conf. (CCC’18), pp. 12:1–16. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018. [doi:10.4230/LIPIcs.CCC.2018.12, ECCC:TR18-095]

[14]   J. Lawrence Carter and Mark N. Wegman: Universal classes of hash functions. J. Comput. System Sci., 18(2):143–154, 1979. Preliminary version in STOC’77. [doi:10.1016/0022-0000(79)90044-8]

[15]   Lijie Chen, Shuichi Hirahara, Igor C. Oliveira, Ján Pich, Ninad Rajgopal, and Rahul Santhanam: Beyond natural proofs: Hardness magnification and locality. In Proc. 11th Innovations in Theoret. Comp. Sci. conf. (ITCS’20), volume 151, pp. 70:1–48. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2020. [doi:10.4230/LIPIcs.ITCS.2020.70]

[16]   Lijie Chen, Dylan M. McKay, Cody D. Murray, and R. Ryan Williams: Relations and equivalences between circuit lower bounds and Karp-Lipton theorems. In Proc. 34th Comput. Complexity Conf. (CCC’19), pp. 30:1–21. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2019. [doi:10.4230/LIPIcs.CCC.2019.30, ECCC:TR19-075]

[17]   Irit Dinur and Or Meir: Toward the KRW composition conjecture: Cubic formula lower bounds via communication complexity. Comput. Complexity, 27(3):375–462, 2018. Preliminary version in CCC’16. [doi:10.1007/s00037-017-0159-x, ECCC:TR16-035]

[18]   Magnus Gausdal Find, Alexander Golovnev, Edward A. Hirsch, and Alexander S. Kulikov: A better-than-3n lower bound for the circuit complexity of an explicit function. In Proc. 57th FOCS, pp. 89–98. IEEE Comp. Soc., 2016. [doi:10.1109/FOCS.2016.19, ECCC:TR15-166]

[19]   Oded Goldreich: Computational Complexity – A Conceptual Perspective. Cambridge Univ. Press, 2008. [doi:10.1017/CBO9780511804106]

[20]   Johan Håstad: The shrinkage exponent of De Morgan formulas is 2. SIAM J. Comput., 27(1):48–64, 1998. [doi:10.1137/S0097539794261556]

[21]   Shuichi Hirahara and Rahul Santhanam: On the average-case complexity of MCSP and its variants. In Proc. 32nd Comput. Complexity Conf. (CCC’17), pp. 7:1–20. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2017. [doi:10.4230/LIPIcs.CCC.2017.7]

[22]   Pavel Hrubeš, Avi Wigderson, and Amir Yehudayoff: Non-commutative circuits and the Sum-of-Squares problem. J. AMS, 24(3):871–898, 2011. Preliminary version in STOC’10. [doi:10.1090/S0894-0347-2011-00694-2, ECCC:TR10-021]

[23]   Rahul Ilango, Bruno Loff, and Igor C. Oliveira: NP-hardness of circuit minimization for multi-output functions. In Proc. 35th Comput. Complexity Conf. (CCC’20), volume 169, pp. 22:1–36. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2020. [doi:10.4230/LIPIcs.CCC.2020.22, ECCC:TR20-021]

[24]   Russell Impagliazzo, Raghu Meka, and David Zuckerman: Pseudorandomness from shrinkage. J. ACM, 66(2):1–16, 2019. Preliminary version in FOCS’12. [doi:10.1145/3230630, ECCC:TR12-057]

[25]   Russell Impagliazzo, Ramamohan Paturi, and Michael E. Saks: Size-depth tradeoffs for threshold circuits. SIAM J. Comput., 26(3):693–707, 1997. [doi:10.1137/S0097539792282965]

[26]   Kazuo Iwama and Hiroki Morizumi: An explicit lower bound of 5n - o(n) for Boolean circuits. In Proc. Internat. Symp. Math. Foundations of Comp. Sci. (MFCS’02), pp. 353–364. Springer, 2002. [doi:10.1007/3-540-45687-2_29]

[27]   Stasys Jukna: Boolean Function Complexity – Advances and Frontiers. Springer, 2012. [doi:10.1007/978-3-642-24508-4]

[28]   Jørn Justesen: Class of constructive asymptotically good algebraic codes. IEEE Trans. Inform. Theory, 18(5):652–656, 1972. [doi:10.1109/TIT.1972.1054893]

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

[30]   Daniel M. Kane and R. Ryan Williams: Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits. In Proc. 48th STOC, pp. 633–643. ACM Press, 2016. [doi:10.1145/2897518.2897636, arXiv:1511.07860, ECCC:TR15-188]

[31]   Ravi Kannan: Circuit-size lower bounds and non-reducibility to sparse sets. Inform. Control, 55(1–3):40–56, 1982. [doi:10.1016/S0019-9958(82)90382-5]

[32]   Ilan Komargodski, Ran Raz, and Avishay Tal: Improved average-case lower bounds for de Morgan formula size: Matching worst-case lower bound. SIAM J. Comput., 46(1):37–57, 2017. [doi:10.1137/15M1048045]

[33]   Jan Krajíček: Extensions of models of PV. In Proc. Logic Colloquium, ASL Lecture Notes in Logic, pp. 104–114. Springer, 1995. [doi:10.1017/9781316716830.011]

[34]   Jan Krajíček: On the Weak Pigeonhole Principle. Fundamenta Mathematicae, 170(1):123–140, 2001. [doi:10.4064/fm170-1-8]

[35]   Jan Krajíček: Dual Weak Pigeonhole Principle, pseudo-surjective functions, and provability of circuit lower bounds. J. Symbolic Logic, 69(1):265–286, 2004. [doi:10.2178/jsl/1080938841]

[36]   Leonid Levin: Randomness conservation inequalities; information and independence in mathematical theories. Inform. Control, 61(1):15–37, 1984. [doi:10.1016/S0019-9958(84)80060-1]

[37]   Richard J. Lipton and R. Ryan Williams: Amplifying circuit lower bounds against polynomial time, with applications. Comput. Complexity, 22(2):311–343, 2013. [doi:10.1007/s00037-013-0069-5]

[38]   Richard J. Lipton and Neal E. Young: Simple strategies for large zero-sum games with applications to complexity theory. In Proc. 26th STOC, pp. 734–740. ACM Press, 1994. [doi:10.1145/195058.195447]

[39]   Florence Jessie MacWilliams and Neil James Alexander Sloane: The Theory of Error-Correcting Codes. Elsevier, 1977.

[40]   Dylan M. McKay, Cody D. Murray, and R. Ryan Williams: Weak lower bounds on resource-bounded compression imply strong separations of complexity classes. In Proc. 51st STOC, pp. 1215–1225. ACM Press, 2019. [doi:10.1145/3313276.3316396]

[41]   Eric Miles and Emanuele Viola: Substitution-permutation networks, pseudorandom functions, and natural proofs. J. ACM, 62(6):46:1–29, 2015. [doi:10.1145/2792978]

[42]   Moritz Müller and Ján Pich: Feasibly constructive proofs of succinct weak circuit lower bounds. Ann. Pure Appl. Logic, 171(2):102735:1–45, 2020. [doi:10.1016/j.apal.2019.102735, ECCC:TR17-144]

[43]   Cody D. Murray and R. Ryan Williams: Circuit lower bounds for nondeterministic quasi-polytime from a new easy witness lemma. SIAM J. Comput., 49(5):300–322, 2019. Preliminary version in STOC’18. [doi:10.1137/18M1195887]

[44]   Èduard Ivanovič Neiporuk: On a Boolean function (russian). Dokl. Akad. Nauk SSSR (Russian), 169(4):765–766, 1966. Math-Net.Ru.

[45]   Igor C. Oliveira, Ján Pich, and Rahul Santhanam: Hardness magnification near state-of-the-art lower bounds. In Proc. 34th Comput. Complexity Conf. (CCC’19), pp. 27:1–29. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2019. [doi:10.4230/LIPIcs.CCC.2019.27, ECCC:TR18-158]

[46]   Igor C. Oliveira and Rahul Santhanam: Hardness magnification for natural problems. In Proc. 59th FOCS, pp. 65–76. IEEE Comp. Soc., 2018. [doi:10.1109/FOCS.2018.00016, ECCC:TR18-139]

[47]   Ján Pich: Complexity Theory in Feasible Mathematics. Ph. D. thesis, Charles University, Prague, 2014. Charles U. Digital Rep.

[48]   Ján Pich: Circuit lower bounds in bounded arithmetics. Ann. Pure Appl. Logic, 166(1):29–45, 2015. [doi:10.1016/j.apal.2014.08.004, ECCC:TR13-077]

[49]   Alexander A. Razborov: On provably disjoint NP-pairs. BRICS Report Ser., 1(36), 1994. [doi:10.7146/brics.v1i36.21607, ECCC:TR94-006]

[50]   Alexander A. Razborov: Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic. Izvestiya Russ. Akad. Sci. Ser. Math. (Russian), 59(1):201–224, 1995. [doi:10.1070/IM1995v059n01ABEH000009]

[51]   Alexander A. Razborov: Pseudorandom generators hard for k-DNF resolution and polynomial calculus. Ann. Math., 182(2):415–472, 2015. [doi:10.4007/annals.2015.181.2.1]

[52]   Alexander A. Razborov and Steven Rudich: Natural proofs. J. Comput. System Sci., 55(1):24–35, 1997. [doi:10.1006/jcss.1997.1494]

[53]   Rahul Santhanam: Circuit lower bounds for Merlin–Arthur classes. SIAM J. Comput., 39(3):1038–1061, 2009. [doi:10.1137/070702680]

[54]   Michael Sipser and Daniel A. Spielman: Expander codes. IEEE Trans. Inform. Theory, 42(6):1710–1722, 1996. [doi:10.1109/18.556667]

[55]   Daniel A. Spielman: Linear-time encodable and decodable error-correcting codes. IEEE Trans. Inform. Theory, 42(6):1723–1731, 1996. [doi:10.1109/18.556668]

[56]   Aravind Srinivasan: On the approximability of clique and related maximization problems. J. Comput. System Sci., 67(3):633–651, 2003. [doi:10.1016/S0022-0000(03)00110-7]

[57]   Larry J. Stockmeyer: The complexity of approximate counting (Preliminary version). In Proc. 15th STOC, pp. 118–126. ACM Press, 1983. [doi:10.1145/800061.808740]

[58]   Avishay Tal: Shrinkage of De Morgan formulae by spectral techniques. In Proc. 55th FOCS, pp. 551–560. IEEE Comp. Soc., 2014. [doi:10.1109/FOCS.2014.65]

[59]   Avishay Tal: The bipartite formula complexity of inner-product is quadratic. Electron. Colloq. Comput. Complexity, TR16-181, 2016. Conf. version FOCS’17. [ECCC]

[60]   Roei Tell: Quantified derandomization of linear threshold circuits. Electron. Colloq. Comput. Complexity, TR17-145, 2017. Conf. version [61]. [ECCC, arXiv:1709.07635]

[61]   Roei Tell: Quantified derandomization of linear threshold circuits. In Proc. 50th STOC, pp. 855–865. ACM Press, 2018. [doi:10.1145/3188745.3188822, arXiv:1709.07635, ECCC:TR17-145]

[62]   Salil P. Vadhan: Pseudorandomness. Found. Trends Theor. Comp. Sci., 7(1–3):1–336, 2012. [doi:10.1561/0400000010]

[63]   Ingo Wegener: The Complexity of Boolean Functions. Wiley, 1987. ECCC.

[64]   Ryan Williams: Nonuniform ACC circuit lower bounds. J. ACM, 61(1):2:1–32, 2014. [doi:10.1145/2559903]