Bounding the Sensitivity of Polynomial Threshold Functions
by Prahladh Harsha, Adam Klivans, and Raghu Meka
Theory of Computing, Volume 10(1), pp. 1-26, 2014
Bibliography with links to cited articles
[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 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]
[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 AC0 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]