{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T05:58:42Z","timestamp":1775282322265,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":62,"publisher":"ACM","license":[{"start":{"date-parts":[[2012,5,19]],"date-time":"2012-05-19T00:00:00Z","timestamp":1337385600000},"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":[[2012,5,19]]},"DOI":"10.1145\/2213977.2214044","type":"proceedings-article","created":{"date-parts":[[2012,5,21]],"date-time":"2012-05-21T15:20:35Z","timestamp":1337613635000},"page":"747-758","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Making polynomials robust to noise"],"prefix":"10.1145","author":[{"given":"Alexander A.","family":"Sherstov","sequence":"first","affiliation":[{"name":"University of California, Los Angeles, Los Angeles, CA, USA"}]}],"member":"320","published-online":{"date-parts":[[2012,5,19]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2005.v001a001"},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1008731.1008735"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2005.06.006"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.10"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01215346"},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502097"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806703"},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/1747597.1748023"},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1017"},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993659"},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276713"},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/795665.796493"},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-006-1313-z"},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2007.18"},{"key":"e_1_3_2_2_15_1","first-page":"120","volume-title":"Proceedings of the Sixteenth Annual IEEE Conference on Computational Complexity (CCC)","author":"Buhrman H.","year":"2001","unstructured":"H. Buhrman and R. de Wolf . Communication complexity lower bounds by polynomials . In Proceedings of the Sixteenth Annual IEEE Conference on Computational Complexity (CCC) , pages 120 -- 130 , 2001 . H. Buhrman and R. de Wolf. Communication complexity lower bounds by polynomials. In Proceedings of the Sixteenth Annual IEEE Conference on Computational Complexity (CCC), pages 120--130, 2001."},{"key":"e_1_3_2_2_16_1","volume-title":"Introduction to Approximation Theory","author":"Cheney E. W.","year":"1982","unstructured":"E. W. Cheney . Introduction to Approximation Theory . Chelsea Publishing , New York , 2 nd edition, 1982 . E. W. Cheney. Introduction to Approximation Theory. Chelsea Publishing, New York, 2nd edition, 1982.","edition":"2"},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/1347082.1347198"},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.72"},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11854-007-0011-3"},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796310102"},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.796377"},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2008.v004a008"},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90102-2"},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(00)00002-8"},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539791195877"},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.312190"},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.2626"},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.51"},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/060654864"},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/1759210.1759241"},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01271266"},{"key":"e_1_3_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/060649057"},{"key":"e_1_3_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/05063235X"},{"key":"e_1_3_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1531"},{"key":"e_1_3_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.07.007"},{"key":"e_1_3_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-007-5010-1"},{"key":"e_1_3_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-010-0296-y"},{"key":"e_1_3_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00019-9"},{"key":"e_1_3_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/s000370050015"},{"key":"e_1_3_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480103434063"},{"key":"e_1_3_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02128670"},{"key":"e_1_3_2_2_42_1","volume-title":"Perceptrons: An Introduction to Computational Geometry","author":"Minsky M. L.","year":"1969","unstructured":"M. L. Minsky and S. A. Papert . Perceptrons: An Introduction to Computational Geometry . MIT Press , Cambridge, Mass ., 1969 . M. L. Minsky and S. A. Papert. Perceptrons: An Introduction to Computational Geometry. MIT Press, Cambridge, Mass., 1969."},{"key":"e_1_3_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.5555\/1009378.1009548"},{"key":"e_1_3_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01263419"},{"key":"e_1_3_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1994.1059"},{"key":"e_1_3_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1985.41"},{"key":"e_1_3_2_2_47_1","first-page":"145","article-title":"Quantum communication complexity of symmetric predicates. Izvestiya of the Russian Academy of Sciences","volume":"67","author":"Razborov A. A.","year":"2002","unstructured":"A. A. Razborov . Quantum communication complexity of symmetric predicates. Izvestiya of the Russian Academy of Sciences , Mathematics , 67 : 145 -- 159 , 2002 . A. A. Razborov. Quantum communication complexity of symmetric predicates. Izvestiya of the Russian Academy of Sciences, Mathematics, 67:145--159, 2002.","journal-title":"Mathematics"},{"key":"e_1_3_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1137\/080744037"},{"key":"e_1_3_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1991.185425"},{"key":"e_1_3_2_2_50_1","volume-title":"An Introduction to the Approximation of Functions","author":"Rivlin T. J.","year":"1981","unstructured":"T. J. Rivlin . An Introduction to the Approximation of Functions . Dover Publications , New York , 1981 . T. J. Rivlin. An Introduction to the Approximation of Functions. Dover Publications, New York, 1981."},{"key":"e_1_3_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1992.267778"},{"key":"e_1_3_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.556671"},{"key":"e_1_3_2_2_53_1","first-page":"59","article-title":"Communication lower bounds using dual polynomials","volume":"95","author":"Sherstov A. A.","year":"2008","unstructured":"A. A. Sherstov . Communication lower bounds using dual polynomials . Bulletin of the EATCS , 95 : 59 -- 93 , 2008 . A. A. Sherstov. Communication lower bounds using dual polynomials. Bulletin of the EATCS, 95:59--93, 2008.","journal-title":"Bulletin of the EATCS"},{"key":"e_1_3_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2008.18"},{"key":"e_1_3_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.5555\/1747597.1748051"},{"key":"e_1_3_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1137\/08071421X"},{"key":"e_1_3_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806762"},{"key":"e_1_3_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.312168"},{"key":"e_1_3_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.5555\/874062.875504"},{"key":"e_1_3_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2003.07.001"},{"key":"e_1_3_2_2_61_1","doi-asserted-by":"publisher","DOI":"10.5555\/792764.793401"},{"key":"e_1_3_2_2_62_1","doi-asserted-by":"publisher","DOI":"10.5555\/2016985.2016989"}],"event":{"name":"STOC'12: Symposium on Theory of Computing","location":"New York New York USA","acronym":"STOC'12","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the forty-fourth annual ACM symposium on Theory of computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2213977.2214044","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2213977.2214044","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:20:54Z","timestamp":1750238454000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2213977.2214044"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,5,19]]},"references-count":62,"alternative-id":["10.1145\/2213977.2214044","10.1145\/2213977"],"URL":"https:\/\/doi.org\/10.1145\/2213977.2214044","relation":{},"subject":[],"published":{"date-parts":[[2012,5,19]]},"assertion":[{"value":"2012-05-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}