A Regularity Lemma and Low-Weight Approximators for Low-Degree Polynomial Threshold Functions

by Ilias Diakonikolas, Rocco A. Servedio, Li-Yang Tan, and Andrew Wan

Theory of Computing, Volume 10(2), pp. 27-53, 2014

Bibliography with links to cited articles

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

[2]   Per Austrin and Johan Hĺstad: Randomly supported independence and resistance. SIAM J. Comput., 40(1):1–27, 2011. Preliminary version in STOC’09. [doi:10.1137/100783534]

[3]   Aline Bonami: Étude des coefficients Fourier des fonctions de Lp(G). Annales de l’Institute Fourier, 20(2):335–402, 1970. EuDML.

[4]   Jehoshua Bruck: Harmonic analysis of polynomial threshold functions. SIAM J. Discrete Math., 3(2):168–177, 1990. [doi:10.1137/0403015]

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

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

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

[8]   Ilias Diakonikolas, Daniel M. Kane, and Jelani Nelson: Bounded independence fools degree-2 threshold functions. In Proc. 51st FOCS, pp. 11–20. IEEE Comp. Soc. Press, 2010. See also at ECCC and arXiv. [doi:10.1109/FOCS.2010.8]

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

[10]   Ilias Diakonikolas and Rocco A. Servedio: Improved approximation of linear threshold functions. Comput. Complexity, 22(3):623–677, 2013. Preliminary version in CCC’09. [doi:10.1007/s00037-012-0045-5]

[11]   Ilias Diakonikolas, Rocco A. Servedio, Li-Yang Tan, and Andrew Wan: A regularity lemma, and low-weight approximators, for low-degree polynomial threshold functions. In Proc. 25th IEEE Conf. on Computational Complexity (CCC’10), pp. 211–222. IEEE Comp. Soc. Press, 2010. [doi:10.1109/CCC.2010.28]

[12]   Irit Dinur, Ehud Friedgut, Guy Kindler, and Ryan O’Donnell: On the Fourier tails of bounded functions over the discrete cube. Israel J. Math., 160(1):389–412, 2007. Preliminary version in STOC’06. [doi:10.1007/s11856-007-0068-9]

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

[14]   Ben Green: A Szemerédi-type regularity lemma in abelian groups, with applications. Geometric and Functional Analysis (GAFA), 15(2):340–376, 2005. See also at arXiv. [doi:10.1007/s00039-005-0509-8]

[15]   Leonard Gross: Logarithmic Sobolev inequalities. Amer. J. Math., 97(4):1061–1083, 1975. JSTOR.

[16]   Prahladh Harsha, Adam Klivans, and Raghu Meka: Bounding the sensitivity of polynomial threshold functions. Theory of Computing, 10(1):1–26, 2014. See also at arXiv. [doi:10.4086/toc.2014.v010a001]

[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]   Gil Kalai and Shmuel Safra: Threshold phenomena and influence. In Computational Complexity and Statistical Physics, pp. 25–60. Oxford Univ. Press, 2006. Available at author’s home page.

[19]   Daniel M. Kane: k-independent Gaussians fool polynomial threshold functions. In Proc. 26th IEEE Conf. on Computational Complexity (CCC’11), pp. 252–261. IEEE Comp. Soc. Press, 2011. See also at arXiv. [doi:10.1109/CCC.2011.13]

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

[21]   Daniel M. Kane: The correct exponent for the Gotsman-Linial conjecture. In Proc. 28th IEEE Conf. on Computational Complexity (CCC’13), pp. 56–64, 2013. See also at arXiv. [doi:10.1109/CCC.2013.15]

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

[23]   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.

[24]   Kevin Matulef, Ryan O’Donnell, Ronitt Rubinfeld, and Rocco A. Servedio: Testing halfspaces. SIAM J. Comput., 39(5):2004–2047, 2010. Preliminary version in SODA’09. See also at ECCC, and related paper in Property Testing. [doi:10.1137/070707890]

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

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

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

[28]   Ryan O’Donnell and Rocco A. Servedio: Extremal properties of polynomial threshold functions. J. Comput. System Sci., 74(3):298–312, 2008. Preliminary version in CCC’03. [doi:10.1016/j.jcss.2007.06.021]

[29]   Ryan O’Donnell and Rocco A. Servedio: New degree bounds for polynomial threshold functions. Combinatorica, 30(3):327–358, 2010. Preliminary version in STOC’03. [doi:10.1007/s00493-010-2173-3]

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

[31]   Vladimir V. Podolskii: Perceptrons of large weight. Problems of Information Transmission, 45(1):46–53, 2009. Preliminary version in CSR’07. [doi:10.1134/S0032946009010062]

[32]   Michael Saks: Slicing the hypercube. In Keith Walker, editor, Surveys in Combinatorics 1993, pp. 211–256. Cambridge Univ. Press, 1993. [doi:10.1017/CBO9780511662089.009]

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

[34]   Alexander A. Sherstov: The intersection of two halfspaces has high threshold degree. In Proc. 50th FOCS, pp. 343–362. IEEE Comp. Soc. Press, 2009. See also at ECCC. [doi:10.1109/FOCS.2009.18]

[35]   Endre Szemerédi: Regular partitions of graphs. Colloq. Internat. CNRS: Problčmes combinatoires et théorie des graphes, 260:399–401, 1978.

[36]   Terence Tao: Structure and randomness in combinatorics. In Proc. 48th FOCS, pp. 3–15. IEEE Comp. Soc. Press, 2007. [doi:10.1109/FOCS.2007.17]

[37]   Ronald de Wolf: A Brief Introduction to Fourier Analysis on the Boolean Cube. Number 1 in Graduate Surveys. Theory of Computing Library, 2008. [doi:10.4086/toc.gs.2008.001]