[1]   Scott Aaronson: A counterexample to the generalized Linial–Nisan conjecture. Electron. Colloq. Comput. Complexity, TR10-109, 2010. [ECCC]

[2]   Scott Aaronson: BQP and the polynomial hierarchy. In Proc. 42nd STOC, pp. 141–150. ACM Press, 2010. [doi:10.1145/1806689.1806711]

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

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

[5]   Miklós Ajtai: Geometric properties of sets defined by constant depth circuits. In Combinatorics, Paul Erdős is Eighty, Vol. 1, Bolyai Soc. Math. Studies, pp. 19–31. J. Bolyai Math. Soc., Budapest, 1993.

[6]   Miklós Ajtai and Avi Wigderson: Deterministic simulation of probabilistic constant depth circuits. Adv. Comput. Res., 5:199–222, 1989. Preliminary version in FOCS’85.

[7]   Noga Alon, László Babai, and Alon Itai: A fast and simple randomized algorithm for the maximal independent set problem. J. Algorithms, 7(4):567–583, 1986. [doi:10.1016/0196-6774(86)90019-2]

[8]   Noga Alon, Oded Goldreich, Johan Håstad, and René Peralta: Simple constructions of almost k-wise independent random variables. Random Struct. Algor., 3(3):289–304, 1992. Preliminary version in FOCS’90. [doi:10.1002/rsa.3240030308]

[9]   Sanjeev Arora and Boaz Barak: Computational Complexity: A modern approach. Cambridge Univ. Press, 2009. [doi:10.1017/CBO9780511804090]

[10]   László Babai: Random oracles separate PSPACE from the polynomial-time hierarchy. Inform. Process. Lett., 26(1):51–53, 1987. [doi:10.1016/0020-0190(87)90036-6]

[11]   László Babai, Noam Nisan, and Márió Szegedy: Multiparty protocols, pseudorandom generators for logspace, and time-space trade-offs. J. Comput. System Sci., 45(2):204–232, 1992. [doi:10.1016/0022-0000(92)90047-M]

[12]    Marshall Ball, Dana Dachman-Soled, Siyao Guo, Tal Malkin, and Li-Yang Tan: Non-malleable codes for small-depth circuits. In Proc. 59th FOCS, pp. 826–837. IEEE Comp. Soc., 2018. [doi:10.1109/FOCS.2018.00083]

[13]   Louay M. J. Bazzi: Polylogarithmic independence can fool DNF formulas. SIAM J. Comput., 38(6):2220–2272, 2009. [doi:10.1137/070691954]

[14]   Paul Beame: Lower bounds for recognizing small cliques on CRCW PRAM’s. Discr. Appl. Math., 29(1):3–20, 1990. [doi:10.1016/0166-218X(90)90079-R]

[15]   Paul Beame: A switching lemma primer. Technical Report UW-CSE-95-07-01, Univ. Washington, 1994. LINK.

[16]   Paul Beame, Russell Impagliazzo, and Srikanth Srinivasan: Approximating AC⁰ by small height decision trees and a deterministic algorithm for #AC⁰-SAT. In Proc. 27th IEEE Conf. on Comput. Complexity (CCC’12), pp. 117–125. IEEE Comp. Soc., 2012. [doi:10.1109/CCC.2012.40]

[17]   Manuel Blum and Silvio Micali: How to construct cryptographically strong sequences of pseudorandom bits. SIAM J. Comput., 13(4):850–864, 1984. Preliminary version in FOCS’82. [doi:10.1137/0213053]

[18]   Andrej Bogdanov: Pseudorandom generators for low degree polynomials. In Proc. 37th STOC, pp. 21–30. ACM Press, 2005. [doi:10.1145/1060590.1060594]

[19]   Andrej Bogdanov and Emanuele Viola: Pseudorandom bits for polynomials. SIAM J. Comput., 39(6):2464–2486, 2010. [doi:10.1137/070712109]

[20]   Jean Bourgain: Estimation of certain exponential sums arising in complexity theory. C. R. Math. Acad. Sci. Paris, 340(9):627–631, 2005. [doi:10.1016/j.crma.2005.03.008]

[21]   Mark Braverman: Polylogarithmic independence fools AC⁰ circuits. J. ACM, 57(5):1–10, 2010. [doi:10.1145/1754399.1754401]

[22]    Jin-Yi Cai: With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy. J. Comput. System Sci., 38(1):68–85, 1989. Preliminary version in STOC’86. [doi:10.1016/0022-0000(89)90033-0]

[23]   Arkadev Chattopadhyay: Discrepancy and the power of bottom fan-in in depth-three circuits. In Proc. 48th FOCS, pp. 449–458. IEEE Comp. Soc., 2007. [doi:10.1109/FOCS.2007.30, ECCC:TR07-050]

[24]   Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, and Shachar Lovett: Pseudorandom generators from polarizing random walks. Theory of Computing, 15(10):1–26, 2019. Preliminary version in CCC’18. [doi:10.4086/toc.2019.v015a010]

[25]    Eshan Chattopadhyay, Pooya Hatami, Shachar Lovett, and Avishay Tal: Pseudorandom generators from the second Fourier level and applications to AC⁰ with parity gates. In Proc. 10th Innovations in Theoret. Comp. Sci. conf. (ITCS’19), pp. 22:1–15. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2019. [doi:10.4230/LIPIcs.ITCS.2019.22]

[26]   Eshan Chattopadhyay and Xin Li: Non-malleable codes and extractors for small-depth circuits, and affine functions. In Proc. 49th STOC, pp. 1171–1184. ACM Press, 2017. [doi:10.1145/3055399.3055483]

[27]    Shiva Chaudhuri and Jaikumar Radhakrishnan: Deterministic restrictions in circuit complexity. In Proc. 28th STOC, pp. 30–36. ACM Press, 1996. [doi:10.1145/237814.237824, ECCC:TR96-004]

[28]   Xi Chen, Igor Carboni Oliveira, Rocco A. Servedio, and Li-Yang Tan: Near-optimal small-depth lower bounds for small distance connectivity. In Proc. 48th STOC, pp. 612–625. ACM Press, 2016. [doi:10.1145/2897518.2897534]

[29]   Anindya De, Omid Etesami, Luca Trevisan, and Madhur Tulsiani: Improved pseudorandom generators for depth 2 circuits. In Proc. 14th Internat. Workshop on Randomization and Computation (RANDOM’10), pp. 504–517. Springer, 2010. [doi:10.1007/978-3-642-15369-3_38]

[30]   Stefan Dziembowski, Krzysztof Pietrzak, and Daniel Wichs: Non-malleable codes. J. ACM, 65(4):20:1–32, 2018. [doi:10.1145/3178432]

[31]   Bill Fefferman, Ronen Shaltiel, Christopher Umans, and Emanuele Viola: On beating the hybrid argument. Theory of Computing, 9(26):809–843, 2013. Preliminary version in ITCS’12. [doi:10.4086/toc.2013.v009a026, ECCC:TR10-186]

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

[33]   Oded Goldreich and Avi Widgerson: On derandomizing algorithms that err extremely rarely. In Proc. 46th STOC, pp. 109–118. ACM Press, 2014. [doi:10.1145/2591796.2591808]

[34]   Parikshit Gopalan, Raghu Meka, and Omer Reingold: DNF sparsification and a faster deterministic counting algorithm. Comput. Complexity, 22(2):275–310, 2013. [doi:10.1007/s00037-013-0068-6]

[35]   Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, and Salil P. Vadhan: Better pseudorandom generators from milder pseudorandom restrictions. In Proc. 53rd FOCS, pp. 120–129. IEEE Comp. Soc., 2012. [doi:10.1109/FOCS.2012.77, arXiv:1210.0049, ECCC:TR12-123]

[36]   Prahladh Harsha and Srikanth Srinivasan: On polynomial approximations to AC⁰. Random Struct. Algor., 54(2):289–303, 2019. Preliminary version in RANDOM’16. [doi:10.1002/rsa.20786]

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

[38]   Johan Håstad: On the correlation of parity and small-depth circuits. SIAM J. Comput., 43(5):1699–1708, 2014. [doi:10.1137/120897432, ECCC:TR12-137]

[39]   Johan Håstad: An average-case depth hierarchy theorem for higher depths. In Proc. 57th FOCS, pp. 79–88. IEEE Comp. Soc., 2016. [doi:10.1109/FOCS.2016.18, ECCC:TR16-041]

[40]   Johan Håstad: On small-depth Frege proofs for Tseitin for grids. J. ACM, 68(1):1–31, 2020. Preliminary version in FOCS’17. [doi:10.1145/3425606, ECCC:TR17-142]

[41]   Johan Håstad and Mikael Goldmann: On the power of small-depth threshold circuits. Comput. Complexity, 1(2):113–129, 1991. [doi:10.1007/BF01272517]

[42]    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):1–27, 2017. Preliminary version in FOCS’15. [doi:10.1145/3095799, ECCC:TR15-065]

[43]   Russell Impagliazzo, William Matthews, and Ramamohan Paturi: A satisfiability algorithm for AC⁰. In Proc. 23rd Ann. ACM–SIAM Symp. on Discrete Algorithms (SODA’12), pp. 961–972. SIAM, 2012. [doi:10.1137/1.9781611973099.77]

[44]   Russell Impagliazzo, Raghu Meka, and David Zuckerman: Pseudorandomness from shrinkage. J. ACM, 66(2):11:1–16, 2019. [doi:10.1145/3230630]

[45]   Adam Klivans: On the derandomization of constant depth circuits. In Proc. 5th Internat. Workshop on Randomization and Computation (RANDOM’01), pp. 249–260. Springer, 2001. [doi:10.1007/3-540-44666-4_28]

[46]   Adam Klivans, Homin Lee, and Andrew Wan: Mansour’s conjecture is true for random DNF formulas. In Proc. 23rd Ann. Conf. on Learning Theory (COLT’10), pp. 368–380. Springer, 2010. [ECCC:TR10-023]

[47]   Jan Krajíček, Pavel Pudlák, and Alan Woods: An exponential lower bound to the size of bounded depth Frege proofs of the pigeonhole principle. Random Struct. Algor., 7(1):15–39, 1995. [doi:10.1002/rsa.3240070103, ECCC:TR94-018]

[48]   Nathan Linial, Yishay Mansour, and Noam Nisan: Constant depth circuits, Fourier transform and learnability. J. ACM, 40(3):607–620, 1993. Preliminary version in FOCS’89. [doi:10.1145/174130.174138]

[49]   Nathan Linial and Noam Nisan: Approximate inclusion-exclusion. Combinatorica, 10(4):349–365, 1990. Preliminary version in STOC’90. [doi:10.1007/BF02128670]

[50]   Shachar Lovett: Unconditional pseudorandom generators for low-degree polynomials. Theory of Computing, 5(3):69–82, 2009. [doi:10.4086/toc.2009.v005a003]

[51]   Shachar Lovett and Srikanth Srinivasan: Correlation bounds for poly-size AC⁰ circuits with n^1-o(1) symmetric gates. In Proc. 15th Internat. Workshop on Randomization and Computation (RANDOM’11), pp. 640–651. Springer, 2011. [doi:10.1007/978-3-642-22935-0_54]

[52]   Chi-Jen Lu: Hitting set generators for sparse polynomials over any finite fields. In Proc. 27th IEEE Conf. on Comput. Complexity (CCC’12), pp. 280–286. IEEE Comp. Soc., 2012. [doi:10.1109/CCC.2012.20]

[53]   Michael Luby and Boban Veličković: On deterministic approximation of DNF. Algorithmica, 16(4–5):415–433, 1996. Preliminary version in STOC’91. [doi:10.1007/BF01940873]

[54]   Michael Luby, Boban Veličković, and Avi Wigderson: Deterministic approximate counting of depth-2 circuits. In Proc. 2nd Isr. Symp. Theory Comp. Sys. (ISTCS’93), pp. 18–24. IEEE Comp. Soc., 1993. [doi:10.1109/ISTCS.1993.253488]

[55]    Raghu Meka, Omer Reingold, and Avishay Tal: Pseudorandom generators for width-3 branching programs. In Proc. 51st STOC, pp. 626–637. ACM Press, 2019. [doi:10.1145/3313276.3316319, arXiv:1806.04256]

[56]   Joseph Naor and Moni Naor: Small-bias probability spaces: Efficient constructions and applications. SIAM J. Comput., 22(4):838–856, 1993. [doi:10.1137/0222053]

[57]   Noam Nisan: Pseudorandom bits for constant depth circuits. Combinatorica, 11(1):63–70, 1991. [doi:10.1007/BF01375474]

[58]   Noam Nisan and Avi Wigderson: Hardness vs. randomness. J. Comput. System Sci., 49(2):149–167, 1994. [doi:10.1016/S0022-0000(05)80043-1]

[59]   Toniann Pitassi, Paul Beame, and Russell Impagliazzo: Exponential lower bounds for the pigeonhole principle. Comput. Complexity, 3(2):97–140, 1993. [doi:10.1007/BF01200117]

[60]   Toniann Pitassi, Benjamin Rossman, Rocco A. Servedio, and Li-Yang Tan: Poly-logarithmic Frege depth lower bounds via an expander switching lemma. In Proc. 48th STOC, pp. 644–657. ACM Press, 2016. [doi:10.1145/2897518.2897637]

[61]   Alexander A. Razborov: Bounded arithmetic and lower bounds in Boolean complexity. In Feasible Mathematics II, pp. 344–386. Springer, 1995. [doi:10.1007/978-1-4612-2566-9_12]

[62]   Alexander A. Razborov: A simple proof of Bazzi’s theorem. ACM Trans. Comput. Theory, 1(1):3:1–5, 2009. [doi:10.1145/1490270.1490273]

[63]   Omer Reingold, Thomas Steinke, and Salil Vadhan: Pseudorandomness for regular branching programs via Fourier analysis. In Proc. 17th Internat. Workshop on Randomization and Computation (RANDOM’13), pp. 655–670. Springer, 2013. [doi:10.1007/978-3-642-40328-6_45]

[64]   Benjamin Rossman: On the constant-depth complexity of k-clique. In Proc. 40th STOC, pp. 721–730. ACM Press, 2008. [doi:10.1145/1374376.1374480]

[65]   Benjamin Rossman: The average sensitivity of bounded-depth formulas. Comput. Complexity, 27(2):209–223, 2018. [doi:10.1007/s00037-017-0156-0]

[66]   Rocco A. Servedio and Li-Yang Tan: What circuit classes can be learned with nontrivial savings? In Proc. 8th Innovations in Theoret. Comp. Sci. conf. (ITCS’17). Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2017. [doi:10.4230/LIPIcs.ITCS.2017.30]

[67]   Rocco A. Servedio and Li-Yang Tan: Luby–Veličković–Wigderson revisited: Improved correlation bounds and pseudorandom generators for depth-two circuits. In Proc. 22nd Internat. Conf. on Randomization and Computation (RANDOM’18), pp. 56:1–20. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018. [doi:10.4230/LIPIcs.APPROX-RANDOM.2018.56]

[68]   Rocco A. Servedio and Li-Yang Tan: Improved pseudorandom generators from pseudorandom multi-switching lemmas. In Proc. 23rd Internat. Conf. on Randomization and Computation (RANDOM’19), pp. 45:1–23. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2019. [doi:10.4230/LIPIcs.APPROX-RANDOM.2019.45]

[69]   Jirí Síma and Stanislav Zák: A polynomial time construction of a hitting set for read-once branching programs of width 3, 2010/2021. [ECCC:TR10-088, arXiv:2101.01151]

[70]   Avishay Tal: Tight bounds on the Fourier spectrum of AC⁰. In Proc. 32nd Comput. Complexity Conf. (CCC’17), pp. 15:1–31. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2017. [doi:10.4230/LIPIcs.CCC.2017.15]

[71]   Neil Thapen: Notes on switching lemmas, 2009. Posted on arXiv in 2022. [arXiv:2202.05651]

[72]   Luca Trevisan: A note on approximate counting for k-DNF. In Proc. 8th Internat. Workshop on Randomization and Computation (RANDOM’04), pp. 417–425. Springer, 2004. [doi:10.1007/978-3-540-27821-4_37]

[73]   Luca Trevisan and Tongke Xue: A derandomized switching lemma and an improved derandomization of AC⁰ . In Proc. 28th IEEE Conf. on Comput. Complexity (CCC’13), pp. 242–247. IEEE Comp. Soc., 2013. [doi:10.1109/CCC.2013.32, ECCC:TR12-116]

[74]   Emanuele Viola: Pseudorandom bits for constant-depth circuits with few arbitrary symmetric gates. SIAM J. Comput., 36(5):1387–1403, 2007. [doi:10.1137/050640941]

[75]   Emanuele Viola: On the power of small-depth computation. Found. Trends Theor. Comp. Sci., 5(1):1–72, 2009. [doi:10.1561/0400000033]

[76]   Emanuele Viola: The sum of d small-bias generators fools polynomials of degree d. Comput. Complexity, 18(2):209–217, 2009. [doi:10.1007/s00037-009-0273-5]

[77]   Emanuele Viola and Avi Wigderson: Norms, XOR lemmas, and lower bounds for polynomials and protocols. Theory of Computing, 4(7):137–168, 2008. [doi:10.4086/toc.2008.v004a007]

[78]   Andrew Yao: Theory and applications of trapdoor functions. In Proc. 23rd FOCS, pp. 80–91. IEEE Comp. Soc., 1982. [doi:10.1109/SFCS.1982.45]

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