{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,19]],"date-time":"2025-11-19T09:09:37Z","timestamp":1763543377947,"version":"3.45.0"},"reference-count":25,"publisher":"Cambridge University Press (CUP)","issue":"6","license":[{"start":{"date-parts":[[2025,8,20]],"date-time":"2025-08-20T00:00:00Z","timestamp":1755648000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2025,11]]},"abstract":"Abstract<\/jats:title>\n \n Let\n \n \n \n $\\Sigma$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n be an alphabet and\n \n \n \n $\\mu$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n be a distribution on\n \n \n \n $\\Sigma ^k$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n for some\n \n \n \n $k \\geqslant 2$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . Let\n \n \n \n $\\alpha \\gt 0$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n be the minimum probability of a tuple in the support of\n \n \n \n $\\mu$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n (denoted\n \n \n \n $\\mathsf{supp}(\\mu )$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n ). We treat the parameters\n \n \n \n $\\Sigma , k, \\mu , \\alpha$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n as fixed and constant. We say that the distribution\n \n \n \n $\\mu$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n has a linear embedding if there exist an Abelian group\n \n \n \n $G$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n (with the identity element\n \n \n \n $0_G$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n ) and mappings\n \n \n \n $\\sigma _i : \\Sigma \\rightarrow G$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n ,\n \n \n \n $1 \\leqslant i \\leqslant k$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , such that at least one of the mappings is non-constant and for every\n \n \n \n $(a_1, a_2, \\ldots , a_k)\\in \\mathsf{supp}(\\mu )$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n ,\n \n \n \n $\\sum _{i=1}^k \\sigma _i(a_i) = 0_G$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . In [Bhangale-Khot-Minzer, STOC 2022], the authors asked the following analytical question. Let\n \n \n \n $f_i: \\Sigma ^n\\rightarrow [\\!-1,1]$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n be bounded functions, such that at least one of the functions\n \n \n \n $f_i$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n essentially has degree at least\n \n \n \n $d$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , meaning that the Fourier mass of\n \n \n \n $f_i$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n on terms of degree less than\n \n \n \n $d$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n is at most\n \n \n \n $\\delta$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . If\n \n \n \n $\\mu$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n has no linear embedding (over any Abelian group), then is it necessarily the case that\n \n \n \n \\begin{equation*}\\left | \\mathop {\\mathbb{E}}_{({\\textbf {x}}_1, {\\textbf {x}}_2, \\ldots , {\\textbf {x}}_k)\\sim \\mu ^{\\otimes n}}[f_1({\\textbf {x}}_1)f_2({\\textbf {x}}_2)\\cdots f_k({\\textbf {x}}_k)] \\right | = o_{d, \\delta }(1),\\end{equation*}<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:disp-formula>\n where the right hand side\n \n \n \n $\\to 0$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n as the degree\n \n \n \n $d \\to \\infty$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n and\n \n \n \n $\\delta \\to 0$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n ?\n <\/jats:p>\n \n In this paper, we answer this analytical question fully and in the affirmative for\n \n \n \n $k=3$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . We also show the following two applications of the result.\n \n \n 1.<\/jats:label>\n \n The first application is related to hardness of approximation. Using the reduction from [5], we show that for every\n \n \n \n $3$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -ary predicate\n \n \n \n $P:\\Sigma ^3 \\to \\{0,1\\}$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n such that\n \n \n \n $P$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n has no linear embedding, an\n SDP (semi-definite programming)\u00a0integrality gap instance<\/jats:italic>\n of a\n \n \n \n $P$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -Constraint Satisfaction Problem (CSP) instance with gap\n \n \n \n $(1,s)$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n can be translated into a dictatorship test with completeness\n \n \n \n $1$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n and soundness\n \n \n \n $s+o(1)$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , under certain additional conditions on the instance.\n <\/jats:p>\n <\/jats:list-item>\n \n 2.<\/jats:label>\n \n The second application is related to additive combinatorics. We show that if the distribution\n \n \n \n $\\mu$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n on\n \n \n \n $\\Sigma ^3$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n has no linear embedding, marginals of\n \n \n \n $\\mu$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n are uniform on\n \n \n \n $\\Sigma$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , and\n \n \n \n $(a,a,a)\\in \\texttt{supp}(\\mu )$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n for every\n \n \n \n $a\\in \\Sigma$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , then every large enough subset of\n \n \n \n $\\Sigma ^n$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n contains a triple\n \n \n \n $({\\textbf {x}}_1, {\\textbf {x}}_2,{\\textbf {x}}_3)$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n from\n \n \n \n $\\mu ^{\\otimes n}$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n (and in fact a significant density of such triples).\n <\/jats:p>\n <\/jats:list-item>\n <\/jats:list>\n <\/jats:p>","DOI":"10.1017\/s0963548325100114","type":"journal-article","created":{"date-parts":[[2025,8,20]],"date-time":"2025-08-20T11:27:07Z","timestamp":1755689227000},"page":"857-926","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":0,"title":["On approximability of satisfiable \n$\\boldsymbol {k}$\n-CSPs: II"],"prefix":"10.1017","volume":"34","author":[{"given":"Amey","family":"Bhangale","sequence":"first","affiliation":[{"name":"University of California"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Subhash","family":"Khot","sequence":"additional","affiliation":[{"name":"New York University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8093-1328","authenticated-orcid":false,"given":"Dor","family":"Minzer","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2025,8,20]]},"reference":[{"key":"S0963548325100114_ref4","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451003"},{"key":"S0963548325100114_ref10","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2017.185.1.7"},{"key":"S0963548325100114_ref8","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(82)90062-0"},{"key":"S0963548325100114_ref9","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3519966"},{"key":"S0963548325100114_ref15","doi-asserted-by":"publisher","DOI":"10.1145\/509907.510017"},{"key":"S0963548325100114_ref17","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-010-0047-x"},{"key":"S0963548325100114_ref2","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-014-0252-0"},{"key":"S0963548325100114_ref5","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520028"},{"key":"S0963548325100114_ref18","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.53"},{"key":"S0963548325100114_ref14","unstructured":"[14] Jones, C. (2016) A noisy-influence regularity lemma for boolean functions. CoRR"},{"key":"S0963548325100114_ref21","doi-asserted-by":"crossref","unstructured":"[21] Raghavendra, P. (2008) Optimal algorithms and inapproximability results for every csp? In Proceedings of the 14th annual Symposium on Theory of Computing (STOC), pp. 245\u2013254.","DOI":"10.1145\/1374376.1374414"},{"key":"S0963548325100114_ref25","first-page":"e2","volume-title":"Forum of Mathematics, Sigma","author":"Tao","year":"2013"},{"key":"S0963548325100114_ref23","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-28.1.104"},{"key":"S0963548325100114_ref3","unstructured":"[3] Bhangale, A. , Harsha, P. and Roy, S. (2022) Mixing of 3-Term Progressions in Quasirandom Groups. In 13th Innovations in Theoretical Computer Science Conference (ITCS), vol. 215, pp. 20:1- 20:9."},{"key":"S0963548325100114_ref13","unstructured":"[13] Haz\u0142a, J. , Holenstein, T. and Mossel, E. (2018) Product space models of correlation: Between noise stability and additive combinatorics. Discrete Analysis (2018). https:\/\/discreteanalysisjournal.com\/article\/6513-product-space-models-of-correlation-between-noise-stability-and-additive-combinatorics"},{"key":"S0963548325100114_ref20","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004117000482"},{"volume-title":"Approximating NP-hard problems efficient algorithms and their limits","year":"2009","author":"Raghavendra","key":"S0963548325100114_ref22"},{"key":"S0963548325100114_ref24","doi-asserted-by":"publisher","DOI":"10.4064\/aa-27-1-199-245"},{"key":"S0963548325100114_ref1","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-2011-00725-X"},{"key":"S0963548325100114_ref12","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548307008826"},{"key":"S0963548325100114_ref6","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00030"},{"key":"S0963548325100114_ref16","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(95)90024-1"},{"key":"S0963548325100114_ref7","unstructured":"[7] Braverman, M. , Khot, S. and Minzer, D. (2021) On Rich 2-to-1 Games. In 12th Innovations in Theoretical Computer Science Conference (ITCS), vol. 185, pp. 27:1- 27:20."},{"key":"S0963548325100114_ref11","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2017.185.1.8"},{"key":"S0963548325100114_ref19","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139814782"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548325100114","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,19]],"date-time":"2025-11-19T09:04:47Z","timestamp":1763543087000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548325100114\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,20]]},"references-count":25,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2025,11]]}},"alternative-id":["S0963548325100114"],"URL":"https:\/\/doi.org\/10.1017\/s0963548325100114","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"type":"print","value":"0963-5483"},{"type":"electronic","value":"1469-2163"}],"subject":[],"published":{"date-parts":[[2025,8,20]]},"assertion":[{"value":"\u00a9 The Author(s), 2025. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}