TY - GEN

T1 - On Approximability of Satisfiable k-CSPs

T2 - 56th Annual ACM Symposium on Theory of Computing, STOC 2024

AU - Bhangale, Amey

AU - Khot, Subhash

AU - Minzer, Dor

N1 - Publisher Copyright:
© 2024 Copyright is held by the owner/author(s). Publication rights licensed to ACM.

PY - 2024/6/10

Y1 - 2024/6/10

N2 - 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.

AB - 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.

KW - Abelian Embeddings

KW - Analysis of Boolean Functions

KW - PCP

UR - http://www.scopus.com/inward/record.url?scp=85196648531&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85196648531&partnerID=8YFLogxK

U2 - 10.1145/3618260.3649610

DO - 10.1145/3618260.3649610

M3 - Conference contribution

AN - SCOPUS:85196648531

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 1423

EP - 1434

BT - STOC 2024 - Proceedings of the 56th Annual ACM Symposium on Theory of Computing

A2 - Mohar, Bojan

A2 - Shinkar, Igor

A2 - O�Donnell, Ryan

PB - Association for Computing Machinery

Y2 - 24 June 2024 through 28 June 2024

ER -