{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T10:19:20Z","timestamp":1781259560645,"version":"3.54.1"},"reference-count":58,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2012,12,1]],"date-time":"2012-12-01T00:00:00Z","timestamp":1354320000000},"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":["J. ACM"],"published-print":{"date-parts":[[2012,12]]},"abstract":"<jats:p>\n            Let\n            <jats:italic>X<\/jats:italic>\n            be randomly chosen from {-1,1}\n            <jats:italic>\n              <jats:sup>n<\/jats:sup>\n            <\/jats:italic>\n            , and let\n            <jats:italic>Y<\/jats:italic>\n            be randomly chosen from the standard spherical Gaussian on \u211d\n            <jats:italic>\n              <jats:sup>n<\/jats:sup>\n            <\/jats:italic>\n            . For any (possibly unbounded) polytope\n            <jats:italic>P<\/jats:italic>\n            formed by the intersection of\n            <jats:italic>k<\/jats:italic>\n            halfspaces, we prove that |Pr[\n            <jats:italic>X<\/jats:italic>\n            \u2208\n            <jats:italic>P<\/jats:italic>\n            ] - Pr[\n            <jats:italic>Y<\/jats:italic>\n            \u2208\n            <jats:italic>P<\/jats:italic>\n            ]| \u2264 log\n            <jats:sup>8\/5<\/jats:sup>\n            <jats:italic>k<\/jats:italic>\n            \u22c5 \u0394, where \u0394 is a parameter that is small for polytopes formed by the intersection of \u201cregular\u201d halfspaces (i.e., halfspaces with low influence). The novelty of our invariance principle is the polylogarithmic dependence on\n            <jats:italic>k<\/jats:italic>\n            . Previously, only bounds that were at least linear in\n            <jats:italic>k<\/jats:italic>\n            were known. The proof of the invariance principle is based on a generalization of the Lindeberg method for proving central limit theorems and could be of use elsewhere.\n          <\/jats:p>\n          <jats:p>We give two important applications of our invariance principle, one from learning theory and the other from pseudorandomness.<\/jats:p>\n          <jats:p>\n            (1) A bound of log\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (1)\n            <\/jats:sup>\n            <jats:italic>k<\/jats:italic>\n            \u22c5 \u03f5\n            <jats:sup>1\/6<\/jats:sup>\n            on the Boolean noise sensitivity of intersections of\n            <jats:italic>k<\/jats:italic>\n            \u201cregular\u201d halfspaces (previous work gave bounds linear in\n            <jats:italic>k<\/jats:italic>\n            ). This gives a corresponding agnostic learning algorithm for intersections of regular halfspaces.\n          <\/jats:p>\n          <jats:p>\n            (2) A pseudorandom generator (PRG) for estimating the Gaussian volume of polytopes with\n            <jats:italic>k<\/jats:italic>\n            faces within error \u03b4 and seed-length\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>n<\/jats:italic>\n            poly(log\n            <jats:italic>k<\/jats:italic>\n            ,1\/\u03b4)).\n          <\/jats:p>\n          <jats:p>We also obtain PRGs with similar parameters that fool polytopes formed by intersection of regular halfspaces over the hypercube. Using our PRG constructions, we obtain the first deterministic quasi-polynomial time algorithms for approximately counting the number of solutions to a broad class of integer programs, including dense covering problems and contingency tables.<\/jats:p>","DOI":"10.1145\/2395116.2395118","type":"journal-article","created":{"date-parts":[[2013,1,8]],"date-time":"2013-01-08T15:34:16Z","timestamp":1357659256000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["An invariance principle for polytopes"],"prefix":"10.1145","volume":"59","author":[{"given":"Prahladh","family":"Harsha","sequence":"first","affiliation":[{"name":"University of Texas, Austin, TX"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Adam","family":"Klivans","sequence":"additional","affiliation":[{"name":"University of Texas, Austin, TX"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Raghu","family":"Meka","sequence":"additional","affiliation":[{"name":"University of Texas, Austin, TX"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2013,1,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132597"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250818"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/070711670"},{"key":"#cr-split#-e_1_2_1_4_1.1","doi-asserted-by":"crossref","unstructured":"Bansal N. and Khot S. 2010. Inapproximability of hypergraph vertex cover and applications to scheduling problems. In Proceedings of the International Colloquim on Automata Languages and Programming (ICALP) S. Abramsky C. Gavoille C. Kirchner F. M. auf der Heide and P. G. Spirakis Eds. Lecture Notes in Computer Science Series vol. 6198. Springer 250--261. http:\/\/dx.doi.org\/10.1007\/978-3-642-14165-2. 10.1007\/978-3-642-14165-2","DOI":"10.1007\/978-3-642-14165-2_22"},{"key":"#cr-split#-e_1_2_1_4_1.2","doi-asserted-by":"crossref","unstructured":"Bansal N. and Khot S. 2010. Inapproximability of hypergraph vertex cover and applications to scheduling problems. In Proceedings of the International Colloquim on Automata Languages and Programming (ICALP) S. Abramsky C. Gavoille C. Kirchner F. M. auf der Heide and P. G. Spirakis Eds. Lecture Notes in Computer Science Series vol. 6198. Springer 250--261. http:\/\/dx.doi.org\/10.1007\/978-3-642-14165-2.","DOI":"10.1007\/978-3-642-14165-2_22"},{"key":"e_1_2_1_5_1","volume-title":"Contemporary Mathematics Series","volume":"453","author":"Barvinok A.","unstructured":"Barvinok , A. and Veomett , E . 2008. The computational complexity of convex bodies. In Surveys on Discrete and Computational Geometry: Twenty Years Later, J. E. Goodman, J. Pach, and R. Pollack, Eds ., Contemporary Mathematics Series , vol. 453 . AMS, 117--137. http:\/\/www.ams.org\/bookstore-getitem\/item=COMM-453, arXiv:math\/0610325. Barvinok, A. and Veomett, E. 2008. The computational complexity of convex bodies. In Surveys on Discrete and Computational Geometry: Twenty Years Later, J. E. Goodman, J. Pach, and R. Pollack, Eds., Contemporary Mathematics Series, vol. 453. AMS, 117--137. http:\/\/www.ams.org\/bookstore-getitem\/item=COMM-453, arXiv:math\/0610325."},{"key":"e_1_2_1_6_1","volume-title":"Continuous Discretely: Integer-point Enumeration in Polyhedra","author":"Beck M.","year":"2007","unstructured":"Beck , M. and Robins , S . 2007 . Computing the Continuous Discretely: Integer-point Enumeration in Polyhedra 1 st Ed. Undergraduate Texts in Mathematics, Springer . http:\/\/math.sfsu.edu\/beck\/ccd.html. Beck, M. and Robins, S. 2007. Computing the Continuous Discretely: Integer-point Enumeration in Polyhedra 1st Ed. Undergraduate Texts in Mathematics, Springer. http:\/\/math.sfsu.edu\/beck\/ccd.html.","edition":"1"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02698830"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00970805"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0378-3758(02)00094-0"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2010.30"},{"key":"e_1_2_1_11_1","unstructured":"Chatterjee S. 2005. A simple invariance theorem. arXiv:math\/0508213.  Chatterjee S. 2005. A simple invariance theorem. arXiv:math\/0508213."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00014-X"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.gs.2008.001"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806763"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.8"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-008-0651-1"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/07068062X"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780643"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/1747597.1748055"},{"key":"e_1_2_1_20_1","volume-title":"An Introduction to Probability Theory and Its Applications","author":"Feller W.","unstructured":"Feller , W. 1968. An Introduction to Probability Theory and Its Applications , Volume 1 3 rd Ed. Wiley . Feller, W. 1968. An Introduction to Probability Theory and Its Applications, Volume 1 3rd Ed. Wiley.","edition":"3"},{"key":"e_1_2_1_21_1","volume-title":"An Introduction to Probability Theory and Its Applications","author":"Feller W.","unstructured":"Feller , W. 1971. An Introduction to Probability Theory and Its Applications , Volume 2 2 nd Ed. Wiley . Feller, W. 1971. An Introduction to Probability Theory and Its Applications, Volume 2 2nd Ed. Wiley.","edition":"2"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/227683.227684"},{"key":"e_1_2_1_23_1","volume-title":"Electron. Colloq. Comput. Complex. (ECCC) 17","author":"Gopalan P.","year":"2010","unstructured":"Gopalan , P. , Klivans , A. , and Meka , R . 2010a. Polynomial-time approximation schemes for knapsack and related counting problems using branching programs . Electron. Colloq. Comput. Complex. (ECCC) 17 , 133. http:\/\/eccc.hpi-web.de\/report\/ 2010 \/133. Gopalan, P., Klivans, A., and Meka, R. 2010a. Polynomial-time approximation schemes for knapsack and related counting problems using branching programs. Electron. Colloq. Comput. Complex. (ECCC) 17, 133. http:\/\/eccc.hpi-web.de\/report\/2010\/133."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2010.29"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806764"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(92)90010-D"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195190"},{"key":"e_1_2_1_29_1","unstructured":"Jerrum M. and Sinclair A. 1997. The Markov chain Monte Carlo method: An approach to approximate counting and integration. In Approximation Algorithms for NP-hard Problems D. S. Hochbaum Ed. PWS Publishing Company. http:\/\/www.ieor.berkeley.edu\/-hochbaum\/html\/book-aanp.html.   Jerrum M. and Sinclair A. 1997. The Markov chain Monte Carlo method: An approach to approximate counting and integration. In Approximation Algorithms for NP-hard Problems D. S. Hochbaum Ed. PWS Publishing Company. http:\/\/www.ieor.berkeley.edu\/-hochbaum\/html\/book-aanp.html."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1988.21923"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/060649057"},{"key":"e_1_2_1_32_1","volume-title":"Noise sensitivity and chaos in social choice theory. Tech. rep. 399","author":"Kalai G.","unstructured":"Kalai , G. 2005. Noise sensitivity and chaos in social choice theory. Tech. rep. 399 , Center for Rationality and Interactive Decision Theory, Hebrew University of Jerusalem . http:\/\/www.ratio.huji.ac.il\/dp_files\/dp-399.pdf. Kalai, G. 2005. Noise sensitivity and chaos in social choice theory. Tech. rep. 399, Center for Rationality and Interactive Decision Theory, Hebrew University of Jerusalem. http:\/\/www.ratio.huji.ac.il\/dp_files\/dp-399.pdf."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00993468"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447372"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.11.002"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.64"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/174130.174138"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796309326"},{"key":"e_1_2_1_39_1","volume-title":"Theoretical Advances in Neural Computation and Learning, V. P. Roychowdhury, K.-Y","author":"Mansour Y.","unstructured":"Mansour , Y. 1994. Learning Boolean functions via the Fourier transform . In Theoretical Advances in Neural Computation and Learning, V. P. Roychowdhury, K.-Y . Siu, and A. Orlitsky, Eds., Kluwer Academic Publishers , 391--424. http:\/\/www.springer.com\/physics\/complexity\/book\/978-0-7923-9478-5. Mansour, Y. 1994. Learning Boolean functions via the Fourier transform. In Theoretical Advances in Neural Computation and Learning, V. P. Roychowdhury, K.-Y. Siu, and A. Orlitsky, Eds., Kluwer Academic Publishers, 391--424. http:\/\/www.springer.com\/physics\/complexity\/book\/978-0-7923-9478-5."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806749"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.44"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-011-0362-7"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.53"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222053"},{"key":"e_1_2_1_45_1","series-title":"Lecture Notes in Mathematics Series","volume-title":"Geometric Aspects of Functional Analysis (Israel Seminar 2001--2002)","author":"Nazarov F.","unstructured":"Nazarov , F. 2003. On the maximal perimeter of a convex set in \u211dn with respect to a Gaussian measure . In Geometric Aspects of Functional Analysis (Israel Seminar 2001--2002) . Lecture Notes in Mathematics Series , vol. 1807\/2003 , Springer , 169--187. Nazarov, F. 2003. On the maximal perimeter of a convex set in \u211dn with respect to a Gaussian measure. In Geometric Aspects of Functional Analysis (Israel Seminar 2001--2002). Lecture Notes in Mathematics Series, vol. 1807\/2003, Springer, 169--187."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.01.001"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374458"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536482"},{"key":"e_1_2_1_49_1","doi-asserted-by":"crossref","unstructured":"Paulauskas V. and Ra\u010dkauskas A. 1989. Approximation Theory in the Central Limit Theorem: Exact Results in Banach Spaces. Kluwer Academic Publishers. (Translated from Russian).  Paulauskas V. and Ra\u010dkauskas A. 1989. Approximation Theory in the Central Limit Theorem: Exact Results in Banach Spaces. Kluwer Academic Publishers. (Translated from Russian).","DOI":"10.1007\/978-94-011-7798-6"},{"key":"e_1_2_1_50_1","unstructured":"Peres Y. 2004. Noise stability of weighted majority. (arXiv:math\/0412377.)  Peres Y. 2004. Noise stability of weighted majority. (arXiv:math\/0412377.)"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1176325373"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374414"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1016\/0047-259X(79)90055-1"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(00)00069-7"},{"key":"e_1_2_1_55_1","unstructured":"Tao T. 2009. Talagrand's concentration inequality. (Post in Blog \u201cWhat's new\u201d). htt:\/\/terrytao.wordpress. com\/2009\/06\/09\/talagrands-concentration-inequality\/.  Tao T. 2009. Talagrand's concentration inequality. (Post in Blog \u201cWhat's new\u201d). htt:\/\/terrytao.wordpress. com\/2009\/06\/09\/talagrands-concentration-inequality\/."},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.4064\/sm180-3-3"},{"key":"e_1_2_1_57_1","series-title":"Graduate texts in Mathematics Series","volume-title":"Lectures on polytopes","author":"Ziegler G. M.","unstructured":"Ziegler , G. M. 1995. Lectures on polytopes . Graduate texts in Mathematics Series , vol. 152 . Springer . http:\/\/www.springer.com\/math\/geometry\/book\/978-0-387-94365-7. Ziegler, G. M. 1995. Lectures on polytopes. Graduate texts in Mathematics Series, vol. 152. Springer. http:\/\/www.springer.com\/math\/geometry\/book\/978-0-387-94365-7."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2395116.2395118","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2395116.2395118","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:34:56Z","timestamp":1750239296000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2395116.2395118"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,12]]},"references-count":58,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2012,12]]}},"alternative-id":["10.1145\/2395116.2395118"],"URL":"https:\/\/doi.org\/10.1145\/2395116.2395118","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,12]]},"assertion":[{"value":"2012-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-01-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}