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

[2]   Andris Ambainis: Quantum lower bounds by quantum arguments. J. Comput. System Sci., 64(4):750–767, 2002. Special issue on STOC 2000 (Portland, OR). [doi:10.1006/jcss.2002.1826]

[3]   Andris Ambainis: Polynomial degree vs. quantum query complexity. J. Comput. System Sci., 72(2):220–238, 2006. [doi:10.1016/j.jcss.2005.06.006]

[4]   Alexander E. Andreev: On a method for obtaining more than quadratic effective lower bounds for the complexity of π-schemes. Moscow University Mathematics Bulletin, 42(1):24–29, 1987. Vestnik Moskov. Univ. Ser. 1: Mat. Mekh. 1987(1) 70–73 (Russian original on Math-net.ru) MR 0883632.

[5]   Boaz Barak, Mark Braverman, Xi Chen, and Anup Rao: How to compress interactive communication. SIAM J. Comput., 42(3):1327–1363, 2013. [doi:10.1137/100811969]

[6]   Paul Beame and Widad Machmouchi: The quantum query complexity of AC. Quantum Inf. Comput., 12(7–8):670–676, 2012. [doi:10.26421/QIC12.7-8-11]

[7]   Maria Luisa Bonet and Samuel R. Buss: Size-depth tradeoffs for Boolean formulae. Inform. Process. Lett., 49(3):151–155, 1994. [doi:10.1016/0020-0190(94)90093-0]

[8]   Richard P. Brent: The parallel evaluation of general arithmetic expressions. J. ACM, 21(2):201–206, 1974. [doi:10.1145/321812.321815]

[9]   Harry Buhrman and Ronald de Wolf: Complexity measures and decision tree complexity: a survey. Theoret. Comput. Sci., 288(1):21–43, 2002. [doi:10.1016/S0304-3975(01)00144-X]

[10]   Andrew M. Childs, Shelby Kimmel, and Robin Kothari: The quantum query complexity of read-many formulas. In Proc. 20th Eur. Symp. Algorithms (ESA’12), pp. 337–348. Springer, 2012. [doi:10.1007/978-3-642-33090-2_30]

[11]   Thomas M. Cover and Joy A. Thomas: Elements of Information Theory. Wiley-Interscience, 1991. [doi:10.1002/047174882X]

[12]   Susanna F. de Rezende, Or Meir, Jakob Nordström, Toniann Pitassi, and Robert Robere: KRW composition theorems via lifting. In Proc. 61st FOCS, pp. 43–49. IEEE Comp. Soc., 2020. [doi:10.1109/FOCS46700.2020.00013, ECCC:TR20-099]

[13]   Irit Dinur and Or Meir: Toward the KRW composition conjecture: Cubic formula lower bounds via communication complexity. Comput. Complexity, 27(3):375–462, 2018. [doi:10.1007/s00037-017-0159-x]

[14]   Jeff Edmonds, Russell Impagliazzo, Steven Rudich, and Jirí Sgall: Communication complexity towards lower bounds on circuit depth. Comput. Complexity, 10(3):210–246, 2001. [doi:10.1007/s00037-001-8195-x]

[15]   Yuval Filmus, Or Meir, and Avishay Tal: Shrinkage under random projections, and cubic formula lower bounds for AC0 (extended abstract). In Proc. 12th Innovations in Theoret. Comp. Sci. Conf. (ITCS’21), pp. 89:1–7. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2021. [doi:10.4230/LIPIcs.ITCS.2021.89]

[16]   Merrick L. Furst, James B. Saxe, and Michael Sipser: Parity, circuits, and the polynomial-time hierarchy. Math. Sys. Theory, 17(1):13–27, 1984. [doi:10.1007/BF01744431]

[17]   Anna Gál, Avishay Tal, and Adrian Trejo Nuñez: Cubic formula size lower bounds based on compositions with majority. In Proc. 10th Innovations in Theoret. Comp. Sci. Conf. (ITCS’19), pp. 35:1–35:13. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2019. [doi:10.4230/LIPIcs.ITCS.2019.35]

[18]   Anat Ganor, Ilan Komargodski, and Ran Raz: The spectrum of small De Morgan formulas. Electron. Colloq. Comput. Complexity, TR12-174, 2012. [ECCC]

[19]   Dmitry Gavinsky, Or Meir, Omri Weinstein, and Avi Wigderson: Toward better formula lower bounds: The composition of a function and a universal relation. SIAM J. Comput., 46(1):114–131, 2017. [doi:10.1137/15M1018319]

[20]   Mikael Goldmann and Johan Håstad: A simple lower bound for monotone clique using a communication game. Inform. Process. Lett., 41(4):221–226, 1992. [doi:10.1016/0020-0190(92)90184-W]

[21]   Mika Göös and Toniann Pitassi: Communication lower bounds via critical block sensitivity. SIAM J. Comput., 47(5):1778–1806, 2018. [doi:10.1137/16M1082007]

[22]   Johan Håstad: Almost optimal lower bounds for small depth circuits. In S. Micali, editor, Randomness and Computation, volume 5 of Adv. Computing Research, pp. 143–170. JAI Press, 1989. DSpace@MIT. Preliminary version in STOC’86.

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

[24]   Johan Håstad, Stasys Jukna, and Pavel Pudlák: Top-down lower bounds for depth-three circuits. Comput. Complexity, 5(2):99–112, 1995. [doi:10.1007/BF01268140]

[25]   Johan Håstad, Benjamin Rossman, Rocco A. Servedio, and Li-Yang Tan: An average-case depth hierarchy theorem for Boolean circuits. J. ACM, 64(5):35:1–27, 2017. Preliminary version in FOCS’15. [doi:10.1145/3095799]

[26]   Johan Håstad and Avi Wigderson: Composition of the universal relation. In Jin yi Cai, editor, Advances In Computational Complexity Theory, volume 13 of DIMACS Ser. in Discr. Math., pp. 119–134. Amer. Math. Soc., 1993. [doi:10.1090/dimacs/013/07]

[27]   Johan Torkel Håstad: Computational limitations of small-depth circuits. Ph. D. thesis, MIT, 1986. Available on author’s website, published as a book by MIT Press, 1987.

[28]   Peter Høyer, Troy Lee, and Robert Špalek: Negative weights make adversaries stronger. In Proc. 39th STOC, pp. 526–535. ACM Press, 2007. [doi:10.1145/1250790.1250867]

[29]   Russell Impagliazzo and Noam Nisan: The effect of random restrictions on formula size. Random Struct. Algor., 4(2):121–134, 1993. [doi:10.1002/rsa.3240040202]

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

[31]   Mauricio Karchmer, Ran Raz, and Avi Wigderson: Super-logarithmic depth lower bounds via the direct sum in communication complexity. Comput. Complexity, 5(3–4):191–204, 1995. [doi:10.1007/BF01206317]

[32]   Mauricio Karchmer and Avi Wigderson: Monotone circuits for connectivity require super-logarithmic depth. SIAM J. Discr. Math., 3(2):255–265, 1990. [doi:10.1137/0403021]

[33]   Valerii Mikhailovich Khrapchenko: A method of obtaining lower bounds for the complexity of π-schemes. Math. Notes. Acad. Sci. USSR (English translation), 10:474–479, 1971. Matem. Zametki 10(1) 83-92, 1971 (Russian original on Math-net.ru). [doi:10.1007/BF01747074]

[34]   Sajin Koroth and Or Meir: Improved composition theorems for functions and relations. In Proc. 22nd Internat. Conf. on Randomization and Computation (RANDOM’18), pp. 48:1–18. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018. [doi:10.4230/LIPIcs.APPROX-RANDOM.2018.48]

[35]   Robin Kothari: Formula size lower bounds for AC0 functions, 2011. Theoretical Computer Science Stack Exchange.

[36]   Elias Koutsoupias: Improvements on Khrapchenko’s theorem. Theoret. Comput. Sci., 116(2):399–403, 1993. [doi:10.1016/0304-3975(93)90330-V]

[37]   Eyal Kushilevitz and Noam Nisan: Communication Complexity. Cambridge Univ. Press, 1997. [doi:10.1017/9781108671644]

[38]   Sophie Laplante, Troy Lee, and Mario Szegedy: The quantum adversary method and classical formula size lower bounds. Comput. Complexity, 15(2):163–196, 2006. [doi:10.1007/s00037-006-0212-7]

[39]   Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Špalek, and Mario Szegedy: Quantum query complexity of state conversion. In Proc. 52nd FOCS, pp. 344–353. IEEE Comp. Soc., 2011. [doi:10.1109/FOCS.2011.75]

[40]   Lily Li and Morgan Shirley: The general adversary bound: A survey, 2021. [arXiv:2104.06380]

[41]   Or Meir: Toward better depth lower bounds: Two results on the multiplexor relation. Comput. Complexity, 29(1):4, 2020. [doi:10.1007/s00037-020-00194-8]

[42]   Ivan Mihajlin and Alexander Smal: Toward better depth lower bounds: The XOR-KRW conjecture. In Proc. 36th Comput. Complexity Conf. (CCC’21), pp. 38:1–24. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2021. [doi:10.4230/LIPIcs.CCC.2021.38]

[43]   Èduard Ivanovič Nečiporuk: On a Boolean function. Soviet Math. Doklady, 7(4):999–1000, 1966. Doklady Akad. Nauk SSSR 169(4), 1966, 765–766 (Russian original on Math-net.ru).

[44]   Mike Paterson and Uri Zwick: Shrinkage of De Morgan formulae under restriction. Random Struct. Algor., 4(2):135–150, 1993. [doi:10.1002/rsa.3240040203]

[45]   Toniann Pitassi and Robert Robere: Strongly exponential lower bounds for monotone computation. In Proc. 49th STOC, pp. 1246–1255. ACM Press, 2017. [doi:10.1145/3055399.3055478]

[46]   Ran Raz and Pierre McKenzie: Separation of the monotone NC hierarchy. Combinatorica, 19(3):403–435, 1999. [doi:10.1007/s004930050062]

[47]   Ran Raz and Avi Wigderson: Monotone circuits for matching require linear depth. J. ACM, 39(3):736–744, 1992. [doi:10.1145/146637.146684]

[48]   Alexander A. Razborov: Applications of matrix methods to the theory of lower bounds in computational complexity. Combinatorica, 10(1):81–93, 1990. [doi:10.1007/BF02122698]

[49]   Ben W. Reichardt: Span programs and quantum query complexity: the general adversary bound is nearly tight for every Boolean function. In Proc. 50th FOCS, pp. 544–551. IEEE Comp. Soc., 2009. [doi:10.1109/FOCS.2009.55]

[50]   Ben W. Reichardt: Reflections for quantum query algorithms. In Proc. 22nd Ann. ACM–SIAM Symp. on Discrete Algorithms (SODA’11), pp. 560–569. SIAM, 2011. [doi:10.1137/1.9781611973082.44]

[51]   Ben W. Reichardt: Span programs are equivalent to quantum query algorithms. SIAM J. Comput., 43(3):1206–1219, 2014. [doi:10.1137/100792640]

[52]   Igor Sergeevich Sergeev: Complexity and depth of formulas for symmetric Boolean functions. Moscow University Mathematics Bulletin, 71(3):127–130, 2016. Vestnik Moskov. Univ. Ser. 1: Mat. Mekh. 2016(3) 53–57 (Russian original on Math-net.ru). [doi:10.3103/S0027132216030098]

[53]   Robert Špalek and Mario Szegedy: All quantum adversary methods are equivalent. Theory of Computing, 2(1):1–18, 2006. [doi:10.4086/toc.2006.v002a001]

[54]   Philip M. Spira: On time-hardware complexity tradeoffs for Boolean functions. In Proc. 4th Hawaii International Symposium on System Sciences, pp. 525–527. Western Periodicals, 1971. Google books.

[55]   Bella Abramovna Subbotovskaya: Realizations of linear functions by formulas using ∨, &, ^-. Soviet Math. Doklady, 2:110–112, 1961. Doklady Akad. Nauk SSSR 136(3), 553–555, 1961 (Russian original on Math-net.ru).

[56]   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]

[57]   Andrew Chi-Chih Yao: Separating the polynomial-time hierarchy by oracles (preliminary version). In Proc. 26th FOCS, pp. 1–10. IEEE Comp. Soc., 1985. [doi:10.1109/SFCS.1985.49]

[58]   Uri Zwick: An extension of Khrapchenko’s theorem. Inform. Process. Lett., 37(4):215–217, 1991. [doi:10.1016/0020-0190(91)90191-J]