{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T02:10:49Z","timestamp":1777428649225,"version":"3.51.4"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2018,4,13]],"date-time":"2018-04-13T00:00:00Z","timestamp":1523577600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000893","name":"Simons Foundation","doi-asserted-by":"crossref","award":["328025"],"award-info":[{"award-number":["328025"]}],"id":[{"id":"10.13039\/100000893","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["DMS 1106999, CCF 1320105 and CCF 1117079"],"award-info":[{"award-number":["DMS 1106999, CCF 1320105 and CCF 1117079"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"DOD ONR","award":["N00014-14-1-0823"],"award-info":[{"award-number":["N00014-14-1-0823"]}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-1128155"],"award-info":[{"award-number":["DMS-1128155"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2018,9,30]]},"abstract":"\n The non-linear invariance principle of Mossel, O\u2019Donnell, and Oleszkiewicz establishes that if\n f<\/jats:italic>\n (\n x<\/jats:italic>\n 1<\/jats:sub>\n ,\u2026 ,\n x<\/jats:italic>\n \n n<\/jats:italic>\n <\/jats:sub>\n ) is a multilinear low-degree polynomial with low influences, then the distribution of if\n f<\/jats:italic>\n (\n b<\/jats:italic>\n 1<\/jats:sub>\n ,\u2026,\n b<\/jats:italic>\n \n n<\/jats:italic>\n <\/jats:sub>\n ) is close (in various senses) to the distribution of\n f<\/jats:italic>\n (\n G<\/jats:italic>\n 1<\/jats:sub>\n ,\u2026,\n G<\/jats:italic>\n \n n<\/jats:italic>\n <\/jats:sub>\n ), where\n B<\/jats:italic>\n i<\/jats:sub>\n \u2208\n R<\/jats:sub>\n {-1,1} are independent Bernoulli random variables and\n G<\/jats:italic>\n i<\/jats:sub>\n \u223c N(0,1) are independent standard Gaussians. The invariance principle has seen many applications in theoretical computer science, including the\n Majority is Stablest<\/jats:italic>\n conjecture, which shows that the Goemans\u2013Williamson algorithm for MAX-CUT is optimal under the Unique Games Conjecture.\n <\/jats:p>\n \n More generally, MOO\u2019s invariance principle works for any two vectors of hypercontractive random variables (\n X<\/jats:italic>\n 1<\/jats:sub>\n ,\u2026 ,\n X<\/jats:italic>\n \n n<\/jats:italic>\n <\/jats:sub>\n ),(\n Y<\/jats:italic>\n 1<\/jats:sub>\n ,\u2026 ,\n Y<\/jats:italic>\n \n n<\/jats:italic>\n <\/jats:sub>\n ) such that (i)\n Matching moments<\/jats:italic>\n :\n X<\/jats:italic>\n \n i<\/jats:italic>\n <\/jats:sub>\n and\n Y<\/jats:italic>\n \n i<\/jats:italic>\n <\/jats:sub>\n have matching first and second moments and (ii)\n Independence<\/jats:italic>\n : the variables\n X<\/jats:italic>\n 1<\/jats:sub>\n ,\u2026 ,\n X<\/jats:italic>\n \n n<\/jats:italic>\n <\/jats:sub>\n are independent, as are\n Y<\/jats:italic>\n 1<\/jats:sub>\n ,\u2026,\n Y<\/jats:italic>\n \n n<\/jats:italic>\n <\/jats:sub>\n .\n <\/jats:p>\n \n The independence condition is crucial to the proof of the theorem, yet in some cases we would like to use distributions\n X<\/jats:italic>\n 1<\/jats:sub>\n ,\u2026 ,\n X<\/jats:italic>\n \n n<\/jats:italic>\n <\/jats:sub>\n in which the individual coordinates are not independent. A common example is the uniform distribution on the\n slice<\/jats:italic>\n (\n \n [\n n<\/jats:italic>\n ]\n <\/jats:sup>\n \n k<\/jats:italic>\n <\/jats:sub>\n ) which consists of all vectors (\n x<\/jats:italic>\n 1<\/jats:sub>\n ,\u2026,\n x<\/jats:italic>\n \n n<\/jats:italic>\n <\/jats:sub>\n )\u2208{0,1}\n \n n<\/jats:italic>\n <\/jats:sup>\n with Hamming weight\u00a0\n k<\/jats:italic>\n . The slice shows up in theoretical computer science (hardness amplification, direct sum testing), extremal combinatorics (Erd\u0151s\u2013Ko\u2013Rado theorems), and coding theory (in the guise of the Johnson association scheme).\n <\/jats:p>\n \n Our main result is an invariance principle in which (\n X<\/jats:italic>\n 1<\/jats:sub>\n ,\u2026,\n X<\/jats:italic>\n \n n<\/jats:italic>\n <\/jats:sub>\n ) is the uniform distribution on a slice (\n \n [\n n<\/jats:italic>\n ]\n <\/jats:sup>\n \n pn<\/jats:italic>\n <\/jats:sub>\n and (\n Y<\/jats:italic>\n 1<\/jats:sub>\n ,\u2026 ,\n Y<\/jats:italic>\n \n n<\/jats:italic>\n <\/jats:sub>\n ) consists either of\n n<\/jats:italic>\n independent Ber(\n p<\/jats:italic>\n ) random variables, or of\n n<\/jats:italic>\n independent N(\n p<\/jats:italic>\n ,\n p<\/jats:italic>\n (1-\n p<\/jats:italic>\n )) random variables. As applications, we prove a version of\n Majority is Stablest<\/jats:italic>\n for functions on the slice, a version of Bourgain\u2019s tail theorem, a version of the Kindler\u2013Safra structural theorem, and a stability version of the\n t<\/jats:italic>\n -intersecting Erd\u0151s\u2013Ko\u2013Rado theorem, combining techniques of Wilson and Friedgut.\n <\/jats:p>\n Our proof relies on a combination of ideas from analysis and probability, algebra, and combinatorics. In particular, we make essential use of recent work of the first author which describes an explicit Fourier basis for the slice.<\/jats:p>","DOI":"10.1145\/3186590","type":"journal-article","created":{"date-parts":[[2018,4,16]],"date-time":"2018-04-16T12:27:57Z","timestamp":1523881677000},"page":"1-37","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Invariance Principle on the Slice"],"prefix":"10.1145","volume":"10","author":[{"given":"Yuval","family":"Filmus","sequence":"first","affiliation":[{"name":"Technion \u2014 Israel Institute of Technology, Haifa, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guy","family":"Kindler","sequence":"additional","affiliation":[{"name":"The Hebrew University, Jerusalem, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Elchanan","family":"Mossel","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, Massachusetts"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Karl","family":"Wimmer","sequence":"additional","affiliation":[{"name":"Duquesne University, Pittsburgh, Pennsylvania"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,4,13]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1006\/eujc.1995.0092"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1006\/aama.1998.0588"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930050042"},{"key":"e_1_2_1_4_1","unstructured":"Eiichi Bannai and Tatsuro Ito. 1984. Algebraic Combinatorics I: Association Schemes. Benjamin\/Cummings Pub. Co. Eiichi Bannai and Tatsuro Ito. 1984. Algebraic Combinatorics I: Association Schemes. Benjamin\/Cummings Pub. Co."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00532234"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2688073.2688078"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488668"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2005.162.439"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1512\/iumj.1976.25.25030"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1090\/pspum\/034\/525324"},{"key":"e_1_2_1_11_1","unstructured":"David Ellis Nathan Keller and Noam Lifshitz. 2016. Stability for the complete intersection theorem and the forbidden intersection problem of Erd\u0151s and S\u00f3s. arXiv:1604.06135. David Ellis Nathan Keller and Noam Lifshitz. 2016. Stability for the complete intersection theorem and the forbidden intersection problem of Erd\u0151s and S\u00f3s. arXiv:1604.06135."},{"key":"e_1_2_1_12_1","unstructured":"David Ellis Nathan Keller and Noam Lifshitz. 2016. Stability versions of Erd\u0151s--Ko--Rado type theorems via Isoperimetry. arXiv:1604.02160. David Ellis Nathan Keller and Noam Lifshitz. 2016. Stability versions of Erd\u0151s--Ko--Rado type theorems via Isoperimetry. arXiv:1604.02160."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1093\/qmath\/12.1.313"},{"key":"e_1_2_1_14_1","unstructured":"Yuval Filmus. 2013. Spectral Methods in Extremal Combinatorics. Ph.D. dissertation. University of Toronto. Yuval Filmus. 2013. Spectral Methods in Extremal Combinatorics. Ph.D. dissertation. University of Toronto."},{"key":"e_1_2_1_15_1","first-page":"P1","article-title":"An orthogonal basis for functions over a slice of the boolean hypercube","volume":"23","author":"Filmus Yuval","year":"2016","journal-title":"Elec. J. Comb."},{"key":"e_1_2_1_16_1","unstructured":"Yuval Filmus and Ferdinand Ihringer. 2018. Boolean constant degree functions on the slice are juntas. CoRR abs\/1801.06338 (2018). arxiv:1801.06338 http:\/\/arxiv.org\/abs\/1801.06338 Yuval Filmus and Ferdinand Ihringer. 2018. Boolean constant degree functions on the slice are juntas. CoRR abs\/1801.06338 (2018). arxiv:1801.06338 http:\/\/arxiv.org\/abs\/1801.06338"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(87)90005-7"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2014.08.006"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(92)90054-X"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-008-2318-9"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-011-0181-7"},{"key":"e_1_2_1_22_1","unstructured":"Nathan Keller and Ohad Klein. 2017. Kindler--Safra theorem for the slice. In Preparation. Nathan Keller and Ohad Klein. 2017. Kindler--Safra theorem for the slice. In Preparation."},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the International Congress of Mathematicians.","author":"Khot Subhash","year":"2010"},{"key":"e_1_2_1_24_1","unstructured":"Guy Kindler. 2002. Property Testing PCP and Juntas. Ph.D. dissertation. Tel-Aviv University. Guy Kindler. 2002. Property Testing PCP and Juntas. Ph.D. dissertation. Tel-Aviv University."},{"key":"e_1_2_1_25_1","unstructured":"Guy Kindler Naomi Kirshner and Ryan O\u2019Donnell. 2014. Gaussian noise sensitivity and Fourier tails. http:\/\/www.cs.cmu.edu\/∼odonnell\/papers\/gaussian-noise-sensitivity.pdf. Guy Kindler Naomi Kirshner and Ryan O\u2019Donnell. 2014. Gaussian noise sensitivity and Fourier tails. http:\/\/www.cs.cmu.edu\/∼odonnell\/papers\/gaussian-noise-sensitivity.pdf."},{"key":"e_1_2_1_26_1","unstructured":"Guy Kindler and Shmuel Safra. 2004. Noise-resistant Boolean functions are juntas. Unpublished manuscript. Guy Kindler and Shmuel Safra. 2004. Noise-resistant Boolean functions are juntas. Unpublished manuscript."},{"key":"e_1_2_1_27_1","first-page":"1855","article-title":"Logarithmic Sobolev inequality for some models of random walks","volume":"26","author":"Lee Tzong-Yau","year":"1998","journal-title":"Ann. Prob."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1979.1055985"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/2982445.2982461"},{"key":"e_1_2_1_30_1","unstructured":"Elchanan Mossel and Yuval Filmus. 2017. Harmonicity and Invariance on Slices of the Boolean Cube. Submitted. Elchanan Mossel and Yuval Filmus. 2017. Harmonicity and Invariance on Slices of the Boolean Cube. Submitted."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2010.171.295"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01263419"},{"key":"e_1_2_1_33_1","unstructured":"Ryan O\u2019Donnell. 2014. Analysis of Boolean Functions. Cambridge University Press. Ryan O\u2019Donnell. 2014. Analysis of Boolean Functions. Cambridge University Press."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2006.10.019"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10801-010-0272-2"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2008.09.010"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579226"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2014.20"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3186590","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3186590","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3186590","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:11:28Z","timestamp":1750212688000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3186590"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,4,13]]},"references-count":38,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,9,30]]}},"alternative-id":["10.1145\/3186590"],"URL":"https:\/\/doi.org\/10.1145\/3186590","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,4,13]]},"assertion":[{"value":"2017-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-04-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}