On Approximability of Satisfiable k-CSPs: II

Amey Bhangale, Subhash Khot, Dor Minzer

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Let ς be an alphabet and μ be a distribution on ςk for some k ≥ 2. Let α > 0 be the minimum probability of a tuple in the support of μ (denoted supp(μ)). Here, the support of μ is the set of all tuples in ςk that have a positive probability mass under μ. We treat the parameters ς, k, μ, α as fixed and constant. We say that the distribution μ has a linear embedding if there exist an Abelian group G (with the identity element 0G) and mappings σi : ς → G, 1 ≤ i ≤ k, such that at least one of the mappings is non-constant and for every (a1, a2, ak) supp(μ), 'i=1k σi(ai) = 0G. Let fi: ςn→ [-1,1] be bounded functions, such that at least one of the functions fi essentially has degree at least d, meaning that the Fourier mass of fi on terms of degree less than d is negligible, say at most-. In particular, |E[fi]| ≤-. The Fourier representation is w.r.t. the marginal of μ on the ith co-ordinate, denoted (ς, μi). If μ has no linear embedding (over any Abelian group), then is it necessarily the case that |E(x1,.,x2,.,.,.,xk)1/4.,μ-.,n[f1(x1)f2(x2)¯.,fk(xk)].,.,=.,od,.,-(1),where the right hand side → 0 as the degree d → ∞ and δ→ 0? In this paper, we answer this analytical question fully and in the affirmative for k=3. We also show the following two applications of the result. The first application is related to hardness of approximation. We show that for every 3-ary predicate P:ς3 → {0,1} such that P has no linear embedding, an SDP integrality gap instance of a P-CSP instance with gap (1,s) can be translated into a dictatorship test with completeness 1 and soundness s+o(1), under certain additional conditions on the instance. The second application is related to additive combinatorics. We show that if the distribution μ on ς3 has no linear embedding, marginals of μ are uniform on ς, and (a,a,a) supp(μ) for every a ς, then every large enough subset of ςn contains a triple (x1, x2,x3) from μ-n (and in fact a significant density of such triples).

Original languageEnglish (US)
Title of host publicationSTOC 2023 - Proceedings of the 55th Annual ACM Symposium on Theory of Computing
EditorsBarna Saha, Rocco A. Servedio
PublisherAssociation for Computing Machinery
Number of pages11
ISBN (Electronic)9781450399135
StatePublished - Jun 2 2023
Event55th Annual ACM Symposium on Theory of Computing, STOC 2023 - Orlando, United States
Duration: Jun 20 2023Jun 23 2023

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017


Conference55th Annual ACM Symposium on Theory of Computing, STOC 2023
Country/TerritoryUnited States


  • constraint satisfaction problems
  • hardness of approximation

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'On Approximability of Satisfiable k-CSPs: II'. Together they form a unique fingerprint.

Cite this