On Approximability of Satisfiable $k$-CSPs: VII

Abstract

Let ${\Sigma }_1,\dots ,{\Sigma }_k$ be finite alphabets, and let $\mu$ be a distribution over ${\Sigma }_1\times \cdots \times {\Sigma }_k$ in which the probability of each atom is at least $\alpha$. We prove that if $\mu$ does not admit Abelian embeddings, and $f_i:{\Sigma }_i\to \mathbb{C}$ are $1$-bounded functions (for $i=1,\dots ,k$) such that \[ \left|\mathbb{E}_{(x_1,\dots,x_k) \sim μ^{\otimes n}}\Big[f_1(x_1) \dots f_k(x_k)\Big]\right| \geq \varepsilon, \] then there exists $L:{\Sigma }_1^n\to \mathbb{C}$ of degree at most $d$ and $\Vert L{\Vert }_2\le 1$ such that $|⟨f_1,L⟩|\ge \delta$, where $d$ and $\delta >0$ depend only on $k,\alpha$ and $\epsilon$. This answers the analytic question posed by Bhangale, Khot, and Minzer (STOC 2022). We also prove several extensions of this result that are useful in subsequent applications.