[1]   Scott Aaronson and Avi Wigderson: Algebrization: A new barrier in complexity theory. ACM Trans. Comput. Theory, 1(1):2:1–2:54, 2009. Conference version in STOC’08. [doi:10.1145/1490270.1490272]

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

[3]   James Aspnes, Richard Beigel, Merrick L. 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]

[4]   László Babai, Noam Nisan, and Mario Szegedy: Multiparty protocols, pseudorandom generators for Logspace, and time-space trade-offs. J. Comput. System Sci., 45(2):204–232, 1992. Conference version in STOC’89. [doi:10.1016/0022-0000(92)90047-M]

[5]   Theodore Baker, John Gill, and Robert Solovay: Relativizations of the P =? NP question. SIAM J. Comput., 4(4):431–442, 1975. [doi:10.1137/0204037]

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

[7]   Ruiwen Chen, Valentine Kabanets, Antonina Kolokolova, Ronen Shaltiel, and David Zuckerman: Mining circuit lower bound proofs for meta-algorithms. Comput. Complexity, 24(2):333–392, 2015. Conference version in CCC’14. [doi:10.1007/s00037-015-0100-0]

[8]   Ruiwen Chen, Rahul Santhanam, and Srikanth Srinivasan: Average-case lower bounds and satisfiability algorithms for small threshold circuits. In Proc. 31st Conf. on Computational Complexity (CCC’16), pp. 1:1–1:35. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2016. [doi:10.4230/LIPIcs.CCC.2016.1]

[9]   Fan R. K. Chung and Lincoln Lu: Survey: Concentration inequalities and martingale inequalities: A survey. Internet Mathematics, 3(1):79–127, 2006. [doi:10.1080/15427951.2006.10129115]

[10]   Thomas M. Cover and Joy A. Thomas: Elements of Information Theory. Wiley Online Library, 2005. [doi:10.1002/047174882X]

[11]   Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco A. Servedio, and Emanuele Viola: Bounded independence fools halfspaces. SIAM J. Comput., 39(8):3441–3462, 2010. Conference version in FOCS’09. [doi:10.1137/100783030]

[12]   Ilias Diakonikolas, Prasad Raghavendra, Rocco A. Servedio, and Li-Yang Tan: Average sensitivity and noise sensitivity of polynomial threshold functions. SIAM J. Comput., 43(1):231–253, 2014. Conference version in STOC’10. [doi:10.1137/110855223, arXiv:0909.5011]

[13]   Devdatt P. Dubhashi and Alessandro Panconesi: Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge Univ. Press, 2009. LINK AT ACM DL.

[14]   William Feller: An Introduction to Probability Theory and Its Applications. John Wiley & Sons, 1968. LINK at Wiley.

[15]   Merrick Furst, James B. Saxe, and Michael Sipser: Parity, circuits, and the polynomial-time hierarchy. Mathematical Systems Theory, 17(1):13–27, 1984. Conference version in FOCS’81. [doi:10.1007/BF01744431]

[16]   Dmitry Gavinsky, Shachar Lovett, Michael E. Saks, and Srikanth Srinivasan: A tail bound for read-k families of functions. Random Struct. Algorithms, 47(1):99–108, 2015. [doi:10.1002/rsa.20532, arXiv:1205.1478]

[17]   Parikshit Gopalan and Rocco A. Servedio: Learning and lower bounds for AC⁰ with threshold gates. In Proc. 13th Internat. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX’10), pp. 588–601. Springer, 2010. [doi:10.1007/978-3-642-15369-3_44]

[18]   Craig Gotsman and Nathan Linial: Spectral properties of threshold functions. Combinatorica, 14(1):35–50, 1994. [doi:10.1007/BF01305949]

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

[20]   Prahladh Harsha, Adam Klivans, and Raghu Meka: Bounding the sensitivity of polynomial threshold functions. Theory of Computing, 10(1):1–26, 2014. Conference version in STOC’10. [doi:10.4086/toc.2014.v010a001, arXiv:0909.5175]

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

[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. [doi:10.1137/1.9781611973099.77, arXiv:1107.3127]

[23]   Russell Impagliazzo, Mohan 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]    Russell Impagliazzo, Ramamohan Paturi, and Michael E. Saks: Size-depth tradeoffs for threshold circuits. SIAM J. Comput., 26(3):693–707, 1997. Conference version in STOC’93. [doi:10.1137/S0097539792282965]

[25]   Svante Janson: Large deviations for sums of partly dependent random variables. Random Struct. Algorithms, 24(3):234–248, 2004. [doi:10.1002/rsa.20008]

[26]   Daniel M. Kane: The correct exponent for the Gotsman–Linial conjecture. Comput. Complexity, 23(2):151–175, 2014. Conference version in CCC’13. [doi:10.1007/s00037-014-0086-z, arXiv:1210.1283]

[27]   Daniel M. Kane and 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]

[28]   Adam R. Klivans, Ryan O’Donnell, and Rocco A. Servedio: Learning intersections and thresholds of halfspaces. J. Comput. System Sci., 68(4):808–840, 2004. Conference version in FOCS’02. [doi:10.1016/j.jcss.2003.11.002]

[29]   Ilan Komargodski and Ran Raz: Average-case lower bounds for formula size. In Proc. 45th STOC, pp. 171–180. ACM Press, 2013. [doi:10.1145/2488608.2488630]

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

[31]   Shachar Lovett and Srikanth Srinivasan: Correlation bounds for poly-size AC⁰ circuits with n^1-o(1) symmetric gates. In Proc. 14th Internat. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX’11), pp. 640–651. Springer, 2011. [doi:10.1007/978-3-642-22935-0_54]

[32]   Raghu Meka and David Zuckerman: Pseudorandom generators for polynomial threshold functions. SIAM J. Comput., 42(3):1275–1301, 2013. Conference version in STOC’10. [doi:10.1137/100811623, arXiv:0910.4122]

[33]   Noam Nisan: Pseudorandom bits for constant depth circuits. Combinatorica, 11(1):63–70, 1991. Conference version in FOCS’88. [doi:10.1007/BF01375474]

[34]   Noam Nisan: The communication complexity of threshold gates. In Combinatorics: Paul Erdös is Eighty, pp. 301–315. János Bolyai Mathematical Society, 1993. Available at author’s website.

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

[36]   Ryan O’Donnell: Hardness amplification within NP. J. Comput. System Sci., 69(1):68–94, 2004. Conference version in CCC’02. [doi:10.1016/j.jcss.2004.01.001]

[37]   Ryan O’Donnell: Analysis of Boolean Functions. Cambridge Univ. Press, 2014. LINK.

[38]   Ryan O’Donnell and Rocco A. Servedio: The Chow parameters problem. SIAM J. Comput., 40(1):165–199, 2011. Conference version in STOC’08. [doi:10.1137/090756466]

[39]   Richard Otter: The number of trees. Ann. of Math., 49(3):583–599, 1948. [doi:10.2307/1969046]

[40]   Ramamohan Paturi, Pavel Pudlák, and Francis Zane: Satisfiability coding lemma. Chicago J. Theoret. Comput. Sci., (11), 1999. Conference version in FOCS’97. [doi:10.4086/cjtcs.1999.011]

[41]   Ramamohan Paturi and Michael E. Saks: Approximating threshold circuits by rational functions. Inform. and Comput., 112(2):257–272, 1994. [doi:10.1006/inco.1994.1059]

[42]   Yuval Peres: Noise stability of weighted majority, 2004. [arXiv:math/0412377]

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

[44]   Anup Rao: Extractors for low-weight affine sources. In Proc. 24th Conf. on Computational Complexity (CCC’09), pp. 95–101. IEEE Comp. Soc. Press, 2009. [doi:10.1109/CCC.2009.36]

[45]   Alexander A. Razborov: Lower bounds on the size of bounded-depth networks over the complete basis with logical addition. Math. Notes of the Acad. Sci. USSR, 41(4):333–338, 1987. [doi:10.1007/BF01137685]

[46]   Alexander A. Razborov and Steven Rudich: Natural proofs. J. Comput. System Sci., 55(1):24–35, 1997. Conference version in STOC’94. [doi:10.1006/jcss.1997.1494]

[47]   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. [doi:10.1016/0020-0190(93)90041-7]

[48]    Vwani Roychowdhury, Kai-Yeung Siu, and Alon Orlitsky: Neural models and spectral methods. In Theoretical Advances in Neural Computation and Learning, pp. 3–36. Springer, 1994. [doi:10.1007/978-1-4615-2696-4_1]

[49]   Rahul Santhanam: Fighting perebor: New and improved algorithms for formula and QBF satisfiability. In Proc. 51st FOCS, pp. 183–192. IEEE Comp. Soc. Press, 2010. [doi:10.1109/FOCS.2010.25]

[50]   Rocco A. Servedio: Every linear threshold function has a low-weight approximator. Comput. Complexity, 16(2):180–209, 2007. Conference version in CCC’06. [doi:10.1007/s00037-007-0228-7]

[51]   Alexander A. Sherstov: Optimal bounds for sign-representing the intersection of two halfspaces by polynomials. Combinatorica, 33(1):73–96, 2013. Conference version in STOC’10. [doi:10.1007/s00493-013-2759-7, arXiv:0910.4224]

[52]   Kai-Yeung Siu, Vwani P. Roychowdhury, and Thomas Kailath: Rational approximation techniques for analysis of neural networks. IEEE Trans. Inform. Theory, 40(2):455–466, 1994. [doi:10.1109/18.312168]

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

[54]   Ryan Williams: New algorithms and lower bounds for circuits with linear threshold gates. In Proc. 46th STOC, pp. 194–202. ACM Press, 2014. [doi:10.1145/2591796.2591858, arXiv:1401.2444]

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

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