[1]   Kazuyuki Amano: Bounds on the size of small depth circuits for approximating majority. In Proc. 36th Internat. Colloq. on Automata, Languages and Programming (ICALP’09), pp. 59–70. Springer, 2009. [doi:10.1007/978-3-642-02927-1_7]

[2]   Sanjeev Arora and Boaz Barak: Computational Complexity - A Modern Approach. Cambridge Univ. Press, 2009. [doi:10.1017/CBO9780511804090]

[3]   Richard Beigel: The polynomial method in circuit complexity. In Proc. 8th IEEE Conf. on Structure in Complexity Theory (SCT’93), pp. 82–95. IEEE Comp. Soc. Press, 1993. [doi:10.1109/SCT.1993.336538]

[4]   Eric Blais and Li-Yang Tan: Approximating Boolean functions with depth-2 circuits. SIAM J. Comput., 44(6):1583–1600, 2015. Preliminary version in CCC’13. [doi:10.1137/14097402X]

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

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

[7]   Shlomo Hoory, Avner Magen, and Toniann Pitassi: Monotone circuits for the majority function. In Proc. Internat. Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (RANDOM’06), pp. 410–425. Springer, 2006. [doi:10.1007/11830924_38]

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

[9]   Mauricio Karchmer and Avi Wigderson: Monotone circuits for connectivity require super-logarithmic depth. SIAM J. Discrete Math., 3(2):255–265, 1990. Preliminary version in STOC’88. [doi:10.1137/0403021]

[10]   Maria M. Klawe, Wolfgang J. Paul, Nicholas Pippenger, and Mihalis Yannakakis: On monotone formulae with restricted depth. In Proc. 16th STOC, pp. 480–487. ACM Press, 1984. [doi:10.1145/800057.808717]

[11]   Swastik Kopparty and Srikanth Srinivasan: Certifying polynomials for AC⁰[⊕] circuits, with applications to lower bounds and circuit compression. Theory of Computing, 14(12):1–24, 2018. Preliminary version in FSTTCS’12. [doi:10.4086/toc.2018.v014a012]

[12]   Ryan O’Donnell and Karl Wimmer: Approximation by DNF: Examples and counterexamples. In Proc. 34th Internat. Colloq. on Automata, Languages and Programming (ICALP’07), pp. 195–206. Springer, 2007. [doi:10.1007/978-3-540-73420-8_19]

[13]   Alexander Alexandrovich Razborov: Lower bounds on the size of bounded depth circuits over a complete basis with logical addition. Mathematical Notes of the Academy of Sciences of the USSR, 41(4):333–338, 1987. Russian original in Mat. Zametki 41(4), 1987, 598–607. [doi:10.1007/BF01137685]

[14]   Benjamin Rossman: The average sensitivity of bounded-depth formulas. Comput. Complexity, 27(2):209–223, 2018. Preliminary version in FOCS’15. [doi:10.1007/s00037-017-0156-0, arXiv:1508.07677]

[15]   Petr Savický and Alan R. Woods: The number of Boolean functions computed by formulas of a given size. Random Structures Algorithms, 13(3–4):349–382, 2000. [doi:10.1002/(SICI)1098-2418(199810/12)13:3/4¡349::AID-RSA9¿3.0.CO;2-V]

[16]   Roman Smolensky: Algebraic methods in the theory of lower bounds for Boolean circuit complexity. In Proc. 19th STOC, pp. 77–82. ACM Press, 1987. [doi:10.1145/28395.28404]

[17]   Roman Smolensky: On representations by low-degree polynomials. In Proc. 34th FOCS, pp. 130–138. IEEE Comp. Soc. Press, 1993. [doi:10.1109/SFCS.1993.366874]

[18]   Mario Szegedy: Algebraic Methods in Lower Bounds for Computational Models with Limited Communication. Ph. D. thesis, University of Chicago, 1989. Available at advisor’s home page.

[19]   Leslie G. Valiant: Short monotone formulae for the majority function. J. Algorithms, 5(3):363–366, 1984. [doi:10.1016/0196-6774(84)90016-6]