{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,13]],"date-time":"2026-07-13T19:32:12Z","timestamp":1783971132133,"version":"3.55.0"},"publisher-location":"New York, NY, USA","reference-count":38,"publisher":"ACM","license":[{"start":{"date-parts":[[2010,6,5]],"date-time":"2010-06-05T00:00:00Z","timestamp":1275696000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2010,6,5]]},"DOI":"10.1145\/1806689.1806763","type":"proceedings-article","created":{"date-parts":[[2010,6,8]],"date-time":"2010-06-08T12:37:34Z","timestamp":1276000654000},"page":"533-542","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":25,"title":["Bounding the average sensitivity and noise sensitivity of polynomial threshold functions"],"prefix":"10.1145","author":[{"given":"Ilias","family":"Diakonikolas","sequence":"first","affiliation":[{"name":"Columbia University, New York, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Prahladh","family":"Harsha","sequence":"additional","affiliation":[{"name":"Tata Institute of Fundamental Research, Mumbai, India"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Adam","family":"Klivans","sequence":"additional","affiliation":[{"name":"University of Texas at Austin, Austin, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Raghu","family":"Meka","sequence":"additional","affiliation":[{"name":"University of Texas at Austin, Austin, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Prasad","family":"Raghavendra","sequence":"additional","affiliation":[{"name":"Microsoft Research, New England, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rocco A.","family":"Servedio","sequence":"additional","affiliation":[{"name":"Columbia University, New York, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Li-Yang","family":"Tan","sequence":"additional","affiliation":[{"name":"Columbia University, New York, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2010,6,5]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536481"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02698830"},{"key":"e_1_3_2_1_3_1","first-page":"193","volume-title":"Proc. 21st Annual Conference on Learning Theory (COLT)","author":"Blais E.","year":"2008","unstructured":"E. Blais , R. O'Donnell , and K. Wimmer . Polynomial regression under arbitrary product distributions . In Proc. 21st Annual Conference on Learning Theory (COLT) , pages 193 -- 204 , 2008 . E. Blais, R. O'Donnell, and K. Wimmer. Polynomial regression under arbitrary product distributions. In Proc. 21st Annual Conference on Learning Theory (COLT), pages 193--204, 2008."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"crossref","DOI":"10.1090\/surv\/062","volume-title":"Gaussian measures. Mathematical surveys and monographs","author":"Bogachev V.","year":"1998","unstructured":"V. Bogachev . Gaussian measures. Mathematical surveys and monographs , vol. 62 , 1998 . V. Bogachev. Gaussian measures. Mathematical surveys and monographs, vol. 62, 1998."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s000390050015"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/234533.234564"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.4310\/MRL.2001.v8.n3.a1"},{"key":"e_1_3_2_1_8_1","volume-title":"Average sensitivity and noise sensitivity of polynomial threshold functions","author":"Diakonikolas I.","year":"2009","unstructured":"I. Diakonikolas , P. Raghavendra , R. Servedio , and L.-Y. Tan . Average sensitivity and noise sensitivity of polynomial threshold functions , 2009 . Available at http:\/\/arxiv.org\/abs\/0909.5011. I. Diakonikolas, P. Raghavendra, R. Servedio, and L.-Y. Tan. Average sensitivity and noise sensitivity of polynomial threshold functions, 2009. Available at http:\/\/arxiv.org\/abs\/0909.5011."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2009.8"},{"key":"e_1_3_2_1_10_1","volume-title":"A regularity lemma, and low-weight approximators, for low-degree polynomial threshold functions. manuscript","author":"Diakonikolas I.","year":"2009","unstructured":"I. Diakonikolas , R. Servedio , L.-Y. Tan , and A. Wan . A regularity lemma, and low-weight approximators, for low-degree polynomial threshold functions. manuscript , 2009 . I. Diakonikolas, R. Servedio, L.-Y. Tan, and A. Wan. A regularity lemma, and low-weight approximators, for low-degree polynomial threshold functions. manuscript, 2009."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/1747597.1748034"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132580"},{"key":"e_1_3_2_1_13_1","volume-title":"An introduction to probability theory and its applications","author":"Feller W.","year":"1968","unstructured":"W. Feller . An introduction to probability theory and its applications . John Wiley & Sons , 1968 . W. Feller. An introduction to probability theory and its applications. John Wiley & Sons, 1968."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009809"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374451"},{"key":"e_1_3_2_1_16_1","volume-title":"Manuscript","author":"Gopalan P.","year":"2009","unstructured":"P. Gopalan and R. Servedio . Learning threshold-of-AC0 circuits . Manuscript , 2009 . P. Gopalan and R. Servedio. Learning threshold-of-AC0 circuits. Manuscript, 2009."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01305949"},{"key":"e_1_3_2_1_18_1","volume-title":"Bounding the sensitivity of polynomial threshold functions.","author":"Harsha P.","year":"2009","unstructured":"P. Harsha , A. Klivans , and R. Meka . Bounding the sensitivity of polynomial threshold functions. Available at http:\/\/arxiv.org\/abs\/0909.5175, 2009 . P. Harsha, A. Klivans, and R. Meka. Bounding the sensitivity of polynomial threshold functions. Available at http:\/\/arxiv.org\/abs\/0909.5175, 2009."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.510018"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511526169","volume-title":"Gaussian Hilbert Spaces","author":"Janson S.","year":"1997","unstructured":"S. Janson . Gaussian Hilbert Spaces . Cambridge University Press , Cambridge, UK , 1997 . S. Janson. Gaussian Hilbert Spaces. Cambridge University Press, Cambridge, UK, 1997."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1988.21923"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/060649057"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374466"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2010.27"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.11.002"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.64"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/174130.174138"},{"key":"e_1_3_2_1_28_1","unstructured":"E.\n      Mossel\n    . \n      Lecture\n     4.\n   Available at http:\/\/www.stat.berkeley.edu\/mossel\/teach\/206af05\/scribes\/sep8.pdf 2005\n  .  E. Mossel. Lecture 4. Available at http:\/\/www.stat.berkeley.edu\/mossel\/teach\/206af05\/scribes\/sep8.pdf 2005."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10097"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.53"},{"key":"e_1_3_2_1_31_1","volume-title":"Lecture 16: The hypercontractivity theorem.","author":"O'Donnell R.","year":"2007","unstructured":"R. O'Donnell . Lecture 16: The hypercontractivity theorem. Available at http:\/\/www.cs.cmu.edu\/odonnell\/boolean-analysis\/lecture16.pdf, 2007 . R. O'Donnell. Lecture 16: The hypercontractivity theorem. Available at http:\/\/www.cs.cmu.edu\/odonnell\/boolean-analysis\/lecture16.pdf, 2007."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.34"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/060669309"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374450"},{"key":"e_1_3_2_1_35_1","unstructured":"Y. Peres. Noise stability of weighted majority 2004.  Y. Peres. Noise stability of weighted majority 2004."},{"key":"e_1_3_2_1_36_1","unstructured":"O. Schramm and J. Steif. Quantitative noise sensitivity and exceptional times for percolation. Ann. Math. to appear.  O. Schramm and J. Steif. Quantitative noise sensitivity and exceptional times for percolation. Ann. Math. to appear."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-007-0228-7"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(00)00069-7"}],"event":{"name":"STOC'10: Symposium on Theory of Computing","location":"Cambridge Massachusetts USA","acronym":"STOC'10","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the forty-second ACM symposium on Theory of computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1806689.1806763","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1806689.1806763","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T11:39:37Z","timestamp":1750246777000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1806689.1806763"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,6,5]]},"references-count":38,"alternative-id":["10.1145\/1806689.1806763","10.1145\/1806689"],"URL":"https:\/\/doi.org\/10.1145\/1806689.1806763","relation":{},"subject":[],"published":{"date-parts":[[2010,6,5]]},"assertion":[{"value":"2010-06-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}