{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:29:12Z","timestamp":1750220952442,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":57,"publisher":"ACM","license":[{"start":{"date-parts":[[2019,6,23]],"date-time":"2019-06-23T00:00:00Z","timestamp":1561248000000},"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":[[2019,6,23]]},"DOI":"10.1145\/3313276.3316321","type":"proceedings-article","created":{"date-parts":[[2019,6,20]],"date-time":"2019-06-20T12:19:08Z","timestamp":1561033148000},"page":"614-625","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Fooling polytopes"],"prefix":"10.1145","author":[{"given":"Ryan","family":"O'Donnell","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, USA"}]},{"given":"Rocco A.","family":"Servedio","sequence":"additional","affiliation":[{"name":"Columbia University, USA"}]},{"given":"Li-Yang","family":"Tan","sequence":"additional","affiliation":[{"name":"Stanford University, USA"}]}],"member":"320","published-online":{"date-parts":[[2019,6,23]]},"reference":[{"key":"e_1_3_2_1_1_1","first-page":"199","article-title":"Deterministic Simulation of Probabilistic Constant Depth Circuits","volume":"5","author":"Ajtai Mikl\u00f3s","year":"1989","unstructured":"Mikl\u00f3s Ajtai and Avi Wigderson . 1989 . Deterministic Simulation of Probabilistic Constant Depth Circuits . Advances in Computing Research 5 (1989), 199 \u2013 222 . Mikl\u00f3s Ajtai and Avi Wigderson. 1989. Deterministic Simulation of Probabilistic Constant Depth Circuits. Advances in Computing Research 5 (1989), 199\u2013222.","journal-title":"Advances in Computing Research"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/070691954"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1017"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00970805"},{"key":"e_1_3_2_1_5_1","unstructured":"Avrim Blum and Ravi Kannan. 1997.  Avrim Blum and Ravi Kannan. 1997."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1475"},{"key":"e_1_3_2_1_7_1","unstructured":"Eshan Chattopadhyay Anindya De and Rocco Servedio. 2018.  Eshan Chattopadhyay Anindya De and Rocco Servedio. 2018."},{"key":"e_1_3_2_1_8_1","unstructured":"Simple and efficient pseudorandom generators from Gaussian processes. Available at https:\/\/eccc.weizmann.ac.il\/report\/2018\/100\/.  Simple and efficient pseudorandom generators from Gaussian processes. Available at https:\/\/eccc.weizmann.ac.il\/report\/2018\/100\/."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/100783030"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.8"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1945-08454-7"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.60"},{"key":"e_1_3_2_1_13_1","volume-title":"Procceedings of the 25th Annual Conference on Learning Theory (COLT). 15","author":"Gopalan Parikshit","year":"2012","unstructured":"Parikshit Gopalan , Adam Klivans , and Raghu Meka . 2012 . Learning Functions of Halfspaces using Prefix Covers . In Procceedings of the 25th Annual Conference on Learning Theory (COLT). 15 .1\u201315.10. Parikshit Gopalan, Adam Klivans, and Raghu Meka. 2012. Learning Functions of Halfspaces using Prefix Covers. In Procceedings of the 25th Annual Conference on Learning Theory (COLT). 15.1\u201315.10."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-013-0068-6"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2010.29"},{"key":"e_1_3_2_1_16_1","unstructured":"Prahladh Harsha Adam R. Klivans and Raghu Meka. 2012.  Prahladh Harsha Adam R. Klivans and Raghu Meka. 2012."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2395116.2395118"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195190"},{"key":"e_1_3_2_1_19_1","unstructured":"Daniel Kane. 2011.  Daniel Kane. 2011."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2011.13"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.16"},{"key":"e_1_3_2_1_22_1","unstructured":"Daniel Kane. 2014.  Daniel Kane. 2014."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591798"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2014.30"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/3235586.3235588"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/110828812"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.06.010"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.11.002"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.64"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.24"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746611"},{"key":"e_1_3_2_1_32_1","volume-title":"On the number of real roots of a random algebraic equation. III. Rec. Math. {Mat. Sbornik} N.S. 12","author":"Littlewood John","year":"1943","unstructured":"John Littlewood and Albert Cyril Offord . 1943. On the number of real roots of a random algebraic equation. III. Rec. Math. {Mat. Sbornik} N.S. 12 ( 1943 ), 277\u2013286. John Littlewood and Albert Cyril Offord. 1943. On the number of real roots of a random algebraic equation. III. Rec. Math. {Mat. Sbornik} N.S. 12 (1943), 277\u2013286."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/100811623"},{"key":"e_1_3_2_1_34_1","unstructured":"Marvin Minsky and Seymour Papert. 1968.  Marvin Minsky and Seymour Papert. 1968."},{"volume-title":"An Introduction to Computational Geometry","author":"Perceptrons","key":"e_1_3_2_1_35_1","unstructured":"Perceptrons : An Introduction to Computational Geometry . MIT Press , Cambridge, MA . Perceptrons: An Introduction to Computational Geometry. MIT Press, Cambridge, MA."},{"key":"e_1_3_2_1_36_1","unstructured":"Fedor Nazarov. 2003.  Fedor Nazarov. 2003."},{"key":"e_1_3_2_1_37_1","volume-title":"Geometric aspects of functional analysis (2001-","author":"On","year":"2002","unstructured":"On the maximal perimeter of a convex set in R n with respect to a Gaussian measure. In Geometric aspects of functional analysis (2001- 2002 ). Lecture Notes in Math., Vol. 1807 , Springer , 169\u2013187. On the maximal perimeter of a convex set in R n with respect to a Gaussian measure. In Geometric aspects of functional analysis (2001- 2002). Lecture Notes in Math., Vol. 1807, Springer, 169\u2013187."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01375474"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01305237"},{"key":"e_1_3_2_1_40_1","unstructured":"Noam Nisan and Avi Wigderson. 1994.  Noam Nisan and Avi Wigderson. 1994."},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80043-1"},{"key":"e_1_3_2_1_42_1","unstructured":"Noam Nisan and David Zuckerman. 1996.  Noam Nisan and David Zuckerman. 1996."},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0004"},{"key":"e_1_3_2_1_44_1","unstructured":"Ryan O\u2019Donnell. 2014.  Ryan O\u2019Donnell. 2014."},{"key":"e_1_3_2_1_45_1","unstructured":"Analysis of Boolean Functions. Cambridge University Press. Available at http:\/\/analysisofbooleanfunctions.net\/.   Analysis of Boolean Functions. Cambridge University Press. Available at http:\/\/analysisofbooleanfunctions.net\/."},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-010-2173-3"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1490270.1490273"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02771562"},{"volume-title":"Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS). 824\u2013835","author":"Rocco","key":"e_1_3_2_1_49_1","unstructured":"Rocco A. Servedio and Li-Yang Tan. 2017. Fooling intersections of low-weight halfspaces . In Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS). 824\u2013835 . Rocco A. Servedio and Li-Yang Tan. 2017. Fooling intersections of low-weight halfspaces. In Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS). 824\u2013835."},{"volume-title":"Proceedings of the 8th Innovations in Theoretical Computer Science (ITCS). 30:1\u201330:21","author":"Rocco","key":"e_1_3_2_1_50_1","unstructured":"Rocco A. Servedio and Li-Yang Tan. 2017. What circuit classes can be learned with non-trivial savings? . In Proceedings of the 8th Innovations in Theoretical Computer Science (ITCS). 30:1\u201330:21 . Rocco A. Servedio and Li-Yang Tan. 2017. What circuit classes can be learned with non-trivial savings?. In Proceedings of the 8th Innovations in Theoretical Computer Science (ITCS). 30:1\u201330:21."},{"key":"e_1_3_2_1_51_1","unstructured":"Alexander A. Sherstov. 2013.  Alexander A. Sherstov. 2013."},{"key":"e_1_3_2_1_52_1","volume-title":"2329\u20132374","author":"Two Halfspaces Has High The Intersection","year":"2013","unstructured":"The Intersection of Two Halfspaces Has High Threshold Degree . SIAM J. Comput . 42, 6 ( 2013 ), 2329\u20132374 . The Intersection of Two Halfspaces Has High Threshold Degree. SIAM J. Comput. 42, 6 (2013), 2329\u20132374."},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-013-2759-7"},{"key":"e_1_3_2_1_54_1","unstructured":"Terence Tao. 2010. 254A Notes: Topics in random matrix theory. (2010).  Terence Tao. 2010. 254A Notes: Topics in random matrix theory. (2010)."},{"key":"e_1_3_2_1_55_1","unstructured":"https: \/\/terrytao.wordpress.com\/tag\/lindebergreplacementtrick\/.  https: \/\/terrytao.wordpress.com\/tag\/lindebergreplacementtrick\/."},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000010"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/1857914.1857916"}],"event":{"name":"STOC '19: 51st Annual ACM SIGACT Symposium on the Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Phoenix AZ USA","acronym":"STOC '19"},"container-title":["Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313276.3316321","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3313276.3316321","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:54:01Z","timestamp":1750204441000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313276.3316321"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,23]]},"references-count":57,"alternative-id":["10.1145\/3313276.3316321","10.1145\/3313276"],"URL":"https:\/\/doi.org\/10.1145\/3313276.3316321","relation":{},"subject":[],"published":{"date-parts":[[2019,6,23]]},"assertion":[{"value":"2019-06-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}