[1]   Noga Alon, Gregory Gutin, and Michael Krivelevich: Algorithms with large domination ratio. J. Algorithms, 50(1):118–131, 2004. [doi:10.1016/j.jalgor.2003.09.003]

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

[3]   Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf: Quantum lower bounds by polynomials. J. ACM, 48(4):778–797, 2001. Preliminary version in FOCS’98. [doi:10.1145/502090.502097]

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

[5]   Michael Ben-Or and Nathan Linial: Collective coin flipping, robust voting schemes and minima of Banzhaf values. In Proc. 26th FOCS, pp. 408–416. IEEE Comp. Soc. Press, 1985. [doi:10.1109/SFCS.1985.15]

[6]   Itai Benjamini, Gil Kalai, and Oded Schramm: Noise sensitivity of Boolean functions and applications to percolation. Inst. Hautes Études Sci. Publ. Math., 90(1):5–43, 1999. See also at arXiv. [doi:10.1007/BF02698830]

[7]   Eric Blais, Ryan O’Donnell, and Karl Wimmer: Polynomial regression under arbitrary product distributions. Machine Learning, 80(2-3):273–294, 2010. Preliminary version in COLT’08. [doi:10.1007/s10994-010-5179-6]

[8]   Anthony Carbery and James Wright: Distributional and L^q norm inequalities for polynomials over convex bodies in Rⁿ. Mathematical Research Letters, 8(3):233–248, 2001. [doi:10.4310/MRL.2001.v8.n3.a1]

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

[10]   Ilias Diakonikolas, Prahladh Harsha, Adam Klivans, Raghu Meka, Prasad Raghavendra, Rocco A. Servedio, and Li-Yang Tan: Bounding the average sensitivity and noise sensitivity of polynomial threshold functions. In Proc. 42nd STOC, pp. 533–542. ACM Press, 2010. [doi:10.1145/1806689.1806763]

[11]   Ilias Diakonikolas, Prasad Raghavendra, Rocco Servedio, and Li-Yang Tan: Average sensitivity and noise sensitivity of polynomial threshold functions. Technical report, 2009. To appear in SIAM J. Comput. [arXiv:0909.5011]

[12]    Ilias Diakonikolas, Rocco A. Servedio, Li-Yang Tan, and Andrew Wan: A regularity lemma and low-weight approximators for low-degree polynomial threshold functions. Theory of Computing, 10(2):27–53, 2014. Preliminary version in CCC’10. See also at arXiv. [doi:10.4086/toc.2014.v010a002]

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

[14]   Johan Håstad: Some optimal inapproximability results. J. ACM, 48(4):798–859, 2001. Preliminary version in STOC’97. [doi:10.1145/502090.502098]

[15]   David Haussler: Decision theoretic generalizations of the PAC model for neural net and other learning applications. Inform. and Comput., 100(1):78–150, 1992. Preliminary version in ALT’90. [doi:10.1016/0890-5401(92)90010-D]

[16]   Svante Janson: Gaussian Hilbert Spaces. Cambridge Univ. Press, 1997. [doi:10.1017/CBO9780511526169]

[17]   Jeff Kahn, Gil Kalai, and Nathan Linial: The influence of variables on Boolean functions. In Proc. 29th FOCS, pp. 68–80. IEEE Comp. Soc. Press, 1988. [doi:10.1109/SFCS.1988.21923]

[18]   Adam Tauman Kalai, Adam R. Klivans, Yishay Mansour, and Rocco A. Servedio: Agnostically learning halfspaces. SIAM J. Comput., 37(6):1777–1805, 2008. Preliminary version in FOCS’05. [doi:10.1137/060649057]

[19]   Gil Kalai: Noise sensitivity and chaos in social choice theory. In Fete of Combinatorics and Computer Science, pp. 173–212. Springer, 2010. [doi:10.1007/978-3-642-13580-4_8]

[20]   Daniel M. Kane: The Gaussian surface area and noise sensitivity of degree-d polynomial threshold functions. Comput. Complexity, 20(2):389–412, 2011. See also at arXiv. [doi:10.1007/s00037-011-0012-6]

[21]   Daniel M. Kane: A structure theorem for poorly anticoncentrated Gaussian chaoses and applications to the study of polynomial threshold functions. In Proc. 53rd FOCS, pp. 91–100. IEEE Comp. Soc. Press, 2012. [doi:10.1109/FOCS.2012.52]

[22]   Michael J. Kearns, Robert E. Schapire, and Linda Sellie: Toward efficient agnostic learning. Machine Learning, 17(2-3):115–141, 1994. Preliminary version in COLT’92. [doi:10.1007/BF00993468]

[23]   Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell: Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? SIAM J. Comput., 37(1):319–357, 2007. Preliminary version in FOCS’04. See also at ECCC. [doi:10.1137/S0097539705447372]

[24]   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. Preliminary version in FOCS’02. [doi:10.1016/j.jcss.2003.11.002]

[25]   Adam R. Klivans, Ryan O’Donnell, and Rocco A. Servedio: Learning geometric concepts via Gaussian surface area. In Proc. 49th FOCS, pp. 541–550. IEEE Comp. Soc. Press, 2008. [doi:10.1109/FOCS.2008.64]

[26]   Adam R. Klivans and Rocco A. Servedio: Learning DNF in time 2^Õ(n1∕3) . J. Comput. System Sci., 68(2):303–318, 2004. Preliminary version in STOC’01. [doi:10.1016/j.jcss.2003.07.007]

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

[28]   Shachar Lovett, Ido Ben-Eliezer, and Ariel Yadin: Polynomial threshold functions: Structure, approximation and pseudorandomness. Electron. Colloq. on Comput. Complexity (ECCC), 16:118, 2009. ECCC. See also at arXiv.

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

[30]   Elchanan Mossel, Ryan O’Donnell, and Krzysztof Oleszkiewicz: Noise stability of functions with low influences: invariance and optimality. Ann. of Math., 171(1):295–341, 2010. Preliminary version in FOCS’05. [doi:10.4007/annals.2010.171.295]

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

[32]   Ryan O’Donnell: Analysis of Boolean Functions. Cambridge Univ. Press, 2014. See online version here.

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

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

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

[36]   Alexander A. Sherstov: The pattern matrix method. SIAM J. Comput., 40(6):1969–2000, 2011. Preliminary version in STOC’08. See also at arXiv. [doi:10.1137/080733644]

[37]   Yaoyun Shi: Lower bounds of quantum black-box complexity and degree of approximating polynomials by influence of Boolean variables. Information Processing Letters, 75(1-2):79–83, 2000. See also at arXiv. [doi:10.1016/S0020-0190(00)00069-7]