[1]   Eric Allender and Vivek Gore: On strong separations from AC⁰. In Proc. 8th Internat. Conf. Fundamentals of Computation Theory (FCT’91), pp. 1–15. Springer, 1991. [doi:10.1007/3-540-54458-5_44]

[2]   James Aspnes, Richard Beigel, Merrick Furst, and Steven Rudich: The expressive power of voting polynomials. Combinatorica, 14(2):135–148, 1994. Conference version in STOC’91. [doi:10.1007/BF01215346]

[3]   David A. Mix Barrington and Howard Straubing: Complex polynomials and circuit lower bounds for modular counting. Comput. Complexity, 4(4):325–338, 1994. Conference version in LATIN’92. [doi:10.1007/BF01263421]

[4]   Paul Beame and Trinh Huynh: Multiparty communication complexity and threshold circuit size of AC⁰. SIAM J. Comput., 41(3):484–518, 2012. Conference version in FOCS’09. [doi:10.1137/100792779]

[5]   Richard Beigel: When do extra majority gates help? Polylog(N) majority gates are equivalent to one. Comput. Complexity, 4(4):314–324, 1994. Conference version in STOC’92. [doi:10.1007/BF01263420]

[6]   Richard Beigel and Jun Tarui: On ACC. Comput. Complexity, 4(4):350–366, 1994. Conference version in FOCS’91. [doi:10.1007/BF01263423]

[7]   Eli Ben-Sasson and Emanuele Viola: Short PCPs with projection queries. In Proc. 41st Internat. Colloq. on Automata, Languages and Programming (ICALP’14), pp. 163–173. Springer, 2014. [doi:10.1007/978-3-662-43948-7_14]

[8]   Ashok K. Chandra, Larry Stockmeyer, and Uzi Vishkin: Constant depth reducibility. SIAM J. Comput., 13(2):423–439, 1984. [doi:10.1137/0213028]

[9]   Arkadev Chattopadhyay and Kristoffer Arnsfelt Hansen: Lower bounds for circuits with few modular and symmetric gates. In Proc. 32nd Internat. Colloq. on Automata, Languages and Programming (ICALP’05), pp. 994–1005. Springer, 2005. [doi:10.1007/11523468_80]

[10]   Gil Cohen: A taste of circuit complexity pivoted at NEXP ⁄⊂ ACC⁰ (and more), 2013. Available at ECCC.

[11]   Don Coppersmith: Rapid multiplication of rectangular matrices. SIAM J. Comput., 11(3):467–471, 1982. [doi:10.1137/0211037]

[12]   Jürgen Forster, Matthias Krause, Satyanarayana V. Lokam, Rustam Mubarakzjanov, Niels Schmitt, and Hans Ulrich Simon: Relations between communication complexity, linear arrangements, and computational complexity. In Proc. 21st Internat. Conf. Foundations of Software Technology and Theoretical Computer Science (FSTTCS’01), pp. 171–182. Springer, 2001. [doi:10.1007/3-540-45294-X_15]

[13]   Mikael Goldmann: On the power of a threshold gate at the top. Inform. Process. Lett., 63(6):287–293, 1997. [doi:10.1016/S0020-0190(97)00141-5]

[14]   Parikshit Gopalan and Rocco A. Servedio: Learning and lower bounds for AC⁰ with threshold gates. In Proc. 14th Internat. Workshop on Randomization and Computation (RANDOM’10), pp. 588–601. Springer, 2010. [doi:10.1007/978-3-642-15369-3_44]

[15]   András Hajnal, Wolfgang Maass, Pavel Pudlák, Mario Szegedy, and György Turán: Threshold circuits of bounded depth. J. Comput. System Sci., 46(2):129–154, 1993. Conference version in FOCS’87. [doi:10.1016/0022-0000(93)90001-D]

[16]   Kristoffer Arnsfelt Hansen: Computing symmetric boolean functions by circuits with few exact threshold gates. In Proc. 13th Ann. Internat. Computing and Combinatorics Conf. (COCOON’07), pp. 448–458. Springer, 2007. [doi:10.1007/978-3-540-73545-8_44]

[17]   Kristoffer Arnsfelt Hansen and Peter Bro Miltersen: Some meet-in-the-middle circuit lower bounds. In Proc. 33rd Internat. Symp. Mathematical Foundations of Comp. Sci. (MFCS’04), pp. 334–345. Springer, 2004. [doi:10.1007/978-3-540-28629-5_24]

[18]   Kristoffer Arnsfelt Hansen and Vladimir V. Podolskii: Exact threshold circuits. In Proc. 25th IEEE Conf. on Computational Complexity (CCC’10), pp. 270–279. IEEE Comp. Soc. Press, 2010. [doi:10.1109/CCC.2010.33]

[19]   Kristoffer Arnsfelt Hansen and Vladimir V. Podolskii: Polynomial threshold functions and boolean threshold circuits. Inform. and Comput., 240:56–73, 2015. Conference version in MFCS’13. [doi:10.1016/j.ic.2014.09.008]

[20]   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. Conference version in CCC’01. [doi:10.1016/S0022-0000(02)00024-7]

[21]   Russell Impagliazzo, Shachar Lovett, Ramamohan Paturi, and Stefan Schneider: 0-1 integer linear programming with a linear number of constraints, 2014. [arXiv:1401.5512]

[22]   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. ACM Press, 2012. ACM DL. [arXiv:1107.3127]

[23]   Russell Impagliazzo, Ramamohan Paturi, and Stefan Schneider: A satisfiability algorithm for sparse depth two threshold circuits. In Proc. 54th FOCS, pp. 479–488. IEEE Comp. Soc. Press, 2013. [doi:10.1109/FOCS.2013.58, arXiv:1212.4548]

[24]   Hamidreza Jahanjou, Eric Miles, and Emanuele Viola: Local reductions, 2013. [arXiv:1311.3171]

[25]   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. Conference version in FSTTCS’12. [doi:10.4086/toc.2018.v014a012]

[26]   Satyanarayana V. Lokam: Complexity lower bounds using linear algebra. Foundations and Trends in Theoretical Computer Science, 4(1-2):1–155, 2009. [doi:10.1561/0400000011]

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

[28]   Alexis Maciel and Denis Thérien: Threshold circuits for iterated multiplication: Using AC⁰ for free. In Proc. 10th Symp. Theoretical Aspects of Comp. Sci. (STACS’93), pp. 545–565. Springer, 1993. [doi:10.1007/3-540-56503-5_54]

[29]   Alexis Maciel and Denis Thérien: Threshold circuits of small majority-depth. Inform. and Comput., 146(1):55–83, 1998. [doi:10.1006/inco.1998.2732]

[30]   Alexis Maciel and Denis Thérien: Efficient threshold circuits for power series. Inform. and Comput., 152(1):62–73, 1999. [doi:10.1006/inco.1998.2783]

[31]   Jiří Matoušek: Computing dominances in Eⁿ. Inform. Process. Lett., 38(5):277–278, 1991. [doi:10.1016/0020-0190(91)90071-O]

[32]   Marvin Minsky and Seymour A. Papert: Perceptrons: An Introduction to Computational Geometry. MIT Press, 1969.

[33]   Saburo Muroga: Threshold Logic and its Applications. John Wiley & Sons, Inc., 1971.

[34]   Saburo Muroga, Iwao Toda, and Satoru Takasu: Theory of majority decision elements. Journal of the Franklin Institute, 271(5):376–418, 1961. [doi:10.1016/0016-0032(61)90702-5]

[35]   Moni Naor and Omer Reingold: Number-theoretic constructions of efficient pseudo-random functions. J. ACM, 51(2):231–262, 2004. Conference version in FOCS’97. [doi:10.1145/972639.972643]

[36]   Noam Nisan: The communication complexity of threshold gates. In Combinatorics, Paul Erds is Eighty, pp. 301–315. János Bolyai Mathematical Society, Budapest, 1994.

[37]   Igor Carboni Oliveira: Algorithms versus circuit lower bounds, 2013. [arXiv:1309.0249]

[38]   Erion Plaku: Multiplicity automata, polynomials and the complexity of small-depth boolean circuits. Master’s thesis, Clarkson University, 2002. Available at robotmotionplanning.org.

[39]   Vladimir V. Podolskii: Exponential lower bound for bounded depth circuits with few threshold gates. Inform. Process. Lett., 112(7):267–271, 2012. [doi:10.1016/j.ipl.2011.12.011]

[40]   Alexander A. Razborov: On small depth threshold circuits. In Proc. 3rd Scandinavian Workshop on Algorithm Theory (SWAT’92), pp. 42–52. Springer, 1992. [doi:10.1007/3-540-55706-7_4]

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

[42]   Alexander A. Razborov and Alexander A. Sherstov: The sign-rank of AC⁰. SIAM J. Comput., 39(5):1833–1855, 2010. Conference version in FOCS’08. [doi:10.1137/080744037]

[43]   Alexander A. Razborov and Avi Wigderson: n^{Ω(log n)} lower bounds on the size of depth-3 threshold circuits with AND gates at the bottom. Inform. Process. Lett., 45(6):303–307, 1993. Conference version in STOC’94. [doi:10.1016/0020-0190(93)90041-7]

[44]   Kenneth W. Regan: Polynomials and combinatorial definitions of languages. In Complexity Theory Retrospective II, pp. 261–293. Springer, 1997.

[45]   John H. Reif and Stephen R. Tate: On threshold circuits and polynomial computation. SIAM J. Comput., 21(5):896–908, 1992. Conference version in SCTC’87. [doi:10.1137/0221053]

[46]   Rahul Santhanam: Ironic complicity: Satisfiability algorithms and circuit lower bounds. Bulletin of the EATCS, 106:31–52, 2012.

[47]   Alexander A. Sherstov: Separating AC⁰ from depth-2 majority circuits. SIAM J. Comput., 38(6):2113–2129, 2009. Conference version in STOC’07. [doi:10.1137/08071421X]

[48]   Kai-Yeung Siu, Jehoshua Bruck, Thomas Kailath, and Thomas Hofmeister: Depth efficient neural networks for division and related problems. IEEE Trans. Inform. Theory, 39(3):946–956, 1993. [doi:10.1109/18.256501]

[49]   Kai-Yeung Siu and Vwani P. Roychowdhury: On optimal depth threshold circuits for multiplication and related problems. SIAM J. Discrete Math., 7(2):284–292, 1994. [doi:10.1137/S0895480192228619]

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

[51]   Emmanuele Viola: Pseudorandom bits for constant-depth circuits with few arbitrary symmetric gates. SIAM J. Comput., 36(5):1387–1403, 2007. Conference version in CCC’05. [doi:10.1137/050640941]

[52]   R. Ryan Williams: Guest column: a casual tour around a circuit complexity bound. ACM SIGACT News, 42(3):54–76, 2011. [doi:10.1145/2034575.2034591, arXiv:1111.1261]

[53]   R. Ryan Williams: Improving exhaustive search implies superpolynomial lower bounds. SIAM J. Comput., 42(3):1218–1244, 2013. Conference version in STOC’10. [doi:10.1137/10080703X]

[54]   R. Ryan Williams: Nonuniform ACC circuit lower bounds. J. ACM, 61(1):2:1–2:32, 2014. Conference version in CCC’11. [doi:10.1145/2559903]

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

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