Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR24-191 | 22nd November 2024 20:47

On Approximability of Satisfiable k-CSPs: VI

RSS-Feed




TR24-191
Authors: Amey Bhangale, Subhash Khot, Yang P. Liu, Dor Minzer
Publication: 22nd November 2024 20:58
Downloads: 139
Keywords: 


Abstract:

We prove local and global inverse theorems for general $3$-wise correlations over pairwise-connected distributions. Let $\mu$ be a distribution over $\Sigma \times \Gamma \times \Phi$ such that the supports of $\mu_{xy}$, $\mu_{xz}$, and $\mu_{yz}$ are all connected, and let $f: \Sigma^n \to \mathbb{C}$, $g: \Gamma^n \to \mathbb{C}$, $h: \Phi^n \to \mathbb{C}$ be $1$-bounded functions satisfying \[ \left|\mathbb{E}_{(x,y,z) \sim \mu^{\otimes n}}[f(x)g(y)h(z)]\right| \geq \varepsilon. \] In this setting, our local inverse theorem asserts that there is $\delta :=exp(-\varepsilon^{-O_{\mu}(1)})$ such that with probability at least $\delta$, a random restriction of $f$ down to $\delta n$ coordinates $\delta$-correlates to a product function. To get a global inverse theorem, we prove a restriction inverse theorem for general product functions, stating that if a random restriction of $f$ down to $\delta n$ coordinates is $\delta$-correlated with a product function with probability at least $\delta$, then $f$ is $2^{-poly(\log(1/\delta))}$-correlated with a function of the form $L\cdot P$, where $L$ is a function of degree $poly(1/\delta)$, $\|L\|_2\leq 1$, and $P$ is a product function.
We show applications to property testing and to additive combinatorics. In particular, we show the following result via a density increment argument. Let $\Sigma$ be a finite set and $S \subseteq \Sigma \times \Sigma \times \Sigma$ such that: (1) $(x, x, x) \in S$ for all $x \in S$, and (2) the supports of $S_{xy}$, $S_{xz}$, and $S_{yz}$ are all connected. Then, any set $A \subseteq \Sigma^n$ with $|\Sigma|^{-n}|A| \geq \Omega((\log \log \log n)^{-c})$ contains $x, y, z \in A$, not all equal, such that $(x_i,y_i,z_i) \in S$ for all $i$. This gives the first reasonable bounds for the restricted 3-AP problem over finite fields.



ISSN 1433-8092 | Imprint