{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:36:32Z","timestamp":1787340992762,"version":"build-2736575974"},"reference-count":39,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2014,1]]},"abstract":"<jats:p>We give the first nontrivial upper bounds on the Boolean average sensitivity and noise sensitivity of degree-$d$ polynomial threshold functions (PTFs). Our bound on the Boolean average sensitivity of PTFs represents the first progress toward the resolution of a conjecture of Gotsman and Linial [Combinatorica, 14 (1994), pp. 35--50], which states that the symmetric function slicing the middle $d$ layers of the Boolean hypercube has the highest average sensitivity of all degree-$d$ PTFs. Via the $L_1$ polynomial regression algorithm of Kalai et al. [SIAM J. Comput., 37 (2008), pp. 1777--1805], our bound on Boolean noise sensitivity yields the first polynomial-time agnostic learning algorithm for the broad class of constant-degree PTFs under the uniform distribution. To obtain our bound on the Boolean average sensitivity of PTFs, we generalize the \u201ccritical-index\u201d machinery of [R. Servedio, Comput. Complexity, 16 (2007), pp. 180--209] (which in that work applies to halfspaces, i.e., degree-1 PTFs) to general PTFs. Together with the \u201cinvariance principle\u201d of [E. Mossel, R. O'Donnell, and K. Oleszkiewicz, Ann. of Math. (2), 171 (2010), pp. 295--341], this allows us to essentially reduce the Boolean setting to the Gaussian setting. The main ingredients used to obtain our bound in the Gaussian setting are tail bounds and anticoncentration bounds on low-degree polynomials in Gaussian random variables [S. Janson, Gaussian Hilbert Spaces, Cambridge University Press, Cambridge, UK, 1997; A. Carbery and J. Wright, Math. Res. Lett., 8 (2001), pp. 233--248]. Our bound on Boolean noise sensitivity is achieved via a simple reduction from upper bounds on average sensitivity of Boolean PTFs to corresponding bounds on noise sensitivity.<\/jats:p>","DOI":"10.1137\/110855223","type":"journal-article","created":{"date-parts":[[2014,2,12]],"date-time":"2014-02-12T13:28:28Z","timestamp":1392211708000},"page":"231-253","source":"Crossref","is-referenced-by-count":15,"title":["Average Sensitivity and Noise Sensitivity of Polynomial Threshold Functions"],"prefix":"10.1137","volume":"43","author":[{"given":"Ilias","family":"Diakonikolas","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Prasad","family":"Raghavendra","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rocco A.","family":"Servedio","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Li-Yang","family":"Tan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2014,2,12]]},"reference":[{"key":"atypb1","first-page":"483","author":"Austrin P.","year":"2009","journal-title":"New York"},{"key":"atypb2","doi-asserted-by":"crossref","unstructured":"W. Beckner,\n                      Inequalities in Fourier analysis\n                      , Ann. of Math. (2), 102 (1975), pp. 159-182.","DOI":"10.2307\/1970980"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1007\/s000390050015"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1007\/BF02698830"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.5802\/aif.357"},{"key":"atypb6","first-page":"193","author":"Blais E.","year":"2008","journal-title":"Finland"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1145\/234533.234564"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.4310\/MRL.2001.v8.n3.a1"},{"key":"atypb9","first-page":"437","author":"Dinur I.","year":"2006","journal-title":"New York"},{"key":"atypb10","first-page":"171","author":"Diakoniokolas I.","year":"2009","journal-title":"NJ"},{"key":"atypb11","first-page":"533","author":"Diakonikolas I.","year":"2010","journal-title":"New York"},{"key":"atypb12","doi-asserted-by":"crossref","unstructured":"I. Diakonikolas, P. Raghavendra, R. Servedio, and L.Y. Tan,\n                      Average Sensitivity and Noise Sensitivity of Polynomial Threshold Functions\n                      , preprint, arXiv:0909.5011, 2009.","DOI":"10.1145\/1806689.1806763"},{"key":"atypb13","first-page":"161","author":"Diakonikolas I.","year":"2009","journal-title":"NJ"},{"key":"atypb14","first-page":"211","author":"Diakonikolas I.","year":"2010","journal-title":"NJ"},{"key":"atypb15","unstructured":"W. Feller,\n                      An Introduction to Probability Theory and Its Applications\n                      , John Wiley, New York, 1968."},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009809"},{"key":"atypb17","first-page":"527","author":"Gopalan P.","year":"2008","journal-title":"New York"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1007\/BF01305949"},{"key":"atypb19","first-page":"588","author":"Gopalan P.","year":"2010","journal-title":"Berlin"},{"key":"atypb20","unstructured":"P. Harsha, A. Klivans, and R. Meka,\n                      Bounding the Sensitivity of Polynomial Threshold Functions\n                      , preprint, arXiv:0909.5175, 2009."},{"key":"atypb21","doi-asserted-by":"crossref","unstructured":"S. Janson,\n                      Gaussian Hilbert Spaces\n                      , Cambridge University Press, Cambridge, UK, 1997.","DOI":"10.1017\/CBO9780511526169"},{"key":"atypb22","first-page":"776","author":"Jackson J.","year":"2002","journal-title":"New York"},{"key":"atypb23","first-page":"205","author":"Kane D. M.","year":"2010","journal-title":"NJ"},{"key":"atypb24","first-page":"68","author":"Kahn J.","year":"1988","journal-title":"NJ"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1137\/060649057"},{"key":"atypb26","first-page":"629","author":"Kalai A.","year":"2008","journal-title":"New York"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.11.002"},{"key":"atypb28","first-page":"541","author":"Klivans A.","year":"2008","journal-title":"NJ"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1145\/174130.174138"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10097"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2010.171.295"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1137\/060669309"},{"key":"atypb33","first-page":"517","author":"O'Donnell R.","year":"2008","journal-title":"New York"},{"key":"atypb34","first-page":"31","author":"O'Donnell R.","year":"2005","journal-title":"NJ"},{"key":"atypb35","unstructured":"Y. Peres,\n                      Noise Stability of Weighted Majority\n                      , preprint, arXiv:0412377, 2004."},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-007-0228-7"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(00)00069-7"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2010.171.619"},{"key":"atypb39","unstructured":"S. Shalev-Shwartz, O. Shamir, and K. Sridharan,\n                      Agnostically Learning Halfspaces with Margin Errors\n                      , Technical Report TTIC-TR-2009-4, Toyota Technological Institute, Chicago, IL, 2009."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/110855223","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:00:00Z","timestamp":1787338800000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/110855223"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,1]]},"references-count":39,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,1]]}},"alternative-id":["10.1137\/110855223"],"URL":"https:\/\/doi.org\/10.1137\/110855223","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,1]]}}}