On approximability of satisfiable $\boldsymbol {k}$ -CSPs: II
Amey Bhangale, Subhash Khot, Dor Minzer · Combinatorics Probability Computing · 2025
Abstract Let $\Sigma$ be an alphabet and $\mu$ be a distribution on $\Sigma ^k$ for some $k \geqslant 2$ . Let $\alpha \gt 0$ be the minimum probability of a tuple in the support of $\mu$ (denoted $\mathsf{supp}(\mu )$ ). We treat the parameters $\Sigma , k, \mu , \alpha$ as fixed and constant. We say that the distribution $\mu$ has a linear embedding if there exist an Abelian group $G$ (with the identity element $0_G$ ) and mappings $\sigma _i : \Sigma \rightarrow G$ , $1 \leqslant i \leqslant k$ , such that at least one of the mappings is non-constant and for every $(a_1, a_2, \ldots , a_k)\in \mathsf{supp}(\mu )$ , $\sum _{i=1}^k \sigma _i(a_i) = 0_G$ . In [Bhangale-Khot-Minzer, STOC 2022], the authors asked the following analytical question. Let $f_i: \Sigma ^n\rightarrow [\!-1,1]$ be bounded functions, such that at least one of the functions $f_i$ essentially has degree at least $d$ , meaning that the Fourier mass of $f_i$ on terms of degree less than $d$ is at most $\delta$ . If $\mu$ has no linear embedding (over any Abelian group), then is it necessarily the case that