On Approximability of Satisfiable k-CSPs: IV

Amey Bhangale, Subhash Khot, Dor Minzer

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


We prove a stability result for general 3-wise correlations over distributions satisfying mild connectivity properties. More concretely, we show that if Σ,Γ and φ are alphabets of constant size, and μ is a distribution over Σ×Γ×φ satisfying: (1) the probability of each atom is at least ω(1), (2) μ is pairwise connected, and (3) μ has no Abelian embeddings into (ℤ,+), then the following holds. Any triplets of 1-bounded functions f: Σn→ℂ, g: Γn→ℂ, h: φn→ℂ satisfying (Formula presented) must arise from an Abelian group associated with the distribution μ. More specifically, we show that there is an Abelian group (H,+) of constant size such that for any such f,g and h, the function f (and similarly g and h) is correlated with a function of the form f(x) = χ(σ(x1),...,σ(xn)) L (x), where σ: Σ → H is some map, χ∈ H⊗n is a character, and L: Σn→ℂ is a low-degree function with bounded 2-norm. En route we prove a few additional results that may be of independent interest, such as an improved direct product theorem, as well as a result we refer to as a "restriction inverse theorem"about the structure of functions that, under random restrictions, with noticeable probability have significant correlation with a product function. In companion papers, we show applications of our results to the fields of Probabilistically Checkable Proofs, as well as various areas in discrete mathematics such as extremal combinatorics and additive combinatorics.

Original languageEnglish (US)
Title of host publicationSTOC 2024 - Proceedings of the 56th Annual ACM Symposium on Theory of Computing
EditorsBojan Mohar, Igor Shinkar, Ryan O�Donnell
PublisherAssociation for Computing Machinery
Number of pages12
ISBN (Electronic)9798400703836
StatePublished - Jun 10 2024
Event56th Annual ACM Symposium on Theory of Computing, STOC 2024 - Vancouver, Canada
Duration: Jun 24 2024Jun 28 2024

Publication series

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


Conference56th Annual ACM Symposium on Theory of Computing, STOC 2024


  • Abelian Embeddings
  • Analysis of Boolean Functions
  • PCP

ASJC Scopus subject areas

  • Software


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

Cite this