ECCC-Report TR23-055https://eccc.weizmann.ac.il/report/2023/055Comments and Revisions published for TR23-055en-usMon, 17 Jul 2023 15:49:40 +0300
Revision 1
| On Approximability of Satisfiable $k$-CSPs: II |
Amey Bhangale,
Subhash Khot,
Dor Minzer
https://eccc.weizmann.ac.il/report/2023/055#revision1Let $\Sigma$ be an alphabet and $\mu$ be a distribution on $\Sigma^k$ for some $k \geq 2$. Let $\alpha > 0$ be the minimum probability of a tuple in the support of $\mu$ (denoted by $supp(\mu)$). Here, the support of $\mu$ is the set of all tuples in $\Sigma^k$ that have a positive probability mass under $\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 \leq i \leq k$, such that at least one of the mappings is non-constant and for every $(a_1, a_2, \ldots, a_k)\in 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 negligible, say at most $\delta$. In particular, $|\mathbb{E}[f_i]| \leq \delta$. The Fourier representation is w.r.t. the marginal of $\mu$ on the $i^{th}$ co-ordinate, denoted $(\Sigma, \mu_i)$. If $\mu$ has no linear embedding (over any Abelian group), then is it necessarily the case that
$$|\mathbb{E}_{(x_1, x_2, \ldots, x_k)\sim \mu^{\otimes n}}[f_1(x_1)f_2(x_2)\cdots f_k(x_k)] = o_{d, \delta}(1),$$
where the right hand side $\to 0$ as the degree $d \to \infty$ and $\delta \to 0$?
In this paper, we answer this analytical question fully and in the affirmative for $k=3$. We also show the following two applications of the result.
1. The first application is related to hardness of approximation. Using the reduction from [Bhangale-Khot-Minzer, STOC 2022], we show that for every $3$-ary predicate $P:\Sigma^3 \to \{0,1\}$ such that $P$ has no linear embedding, an SDP integrality gap instance of a $P$-CSP instance with gap $(1,s)$ can be translated into a dictatorship test with completeness $1$ and soundness $s+o(1)$, under certain additional conditions on the instance.
2. The second application is related to additive combinatorics. We show that if the distribution $\mu$ on $\Sigma^3$ has no linear embedding, marginals of $\mu$ are uniform on $\Sigma$, and $(a,a,a)\in supp(\mu)$ for every $a\in \Sigma$, then every large enough subset of $\Sigma^n$ contains a triple $(x_1, x_2,x_3)$ from $\mu^{\otimes n}$ (and in fact a significant density of such triples).Mon, 17 Jul 2023 15:49:40 +0300https://eccc.weizmann.ac.il/report/2023/055#revision1
Paper TR23-055
| On Approximability of Satisfiable $k$-CSPs: II |
Amey Bhangale,
Subhash Khot,
Dor Minzer
https://eccc.weizmann.ac.il/report/2023/055Let $\Sigma$ be an alphabet and $\mu$ be a distribution on $\Sigma^k$ for some $k \geq 2$. Let $\alpha > 0$ be the minimum probability of a tuple in the support of $\mu$ (denoted by $supp(\mu)$). Here, the support of $\mu$ is the set of all tuples in $\Sigma^k$ that have a positive probability mass under $\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 \leq i \leq k$, such that at least one of the mappings is non-constant and for every $(a_1, a_2, \ldots, a_k)\in 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 negligible, say at most $\delta$. In particular, $|\mathbb{E}[f_i]| \leq \delta$. The Fourier representation is w.r.t. the marginal of $\mu$ on the $i^{th}$ co-ordinate, denoted $(\Sigma, \mu_i)$. If $\mu$ has no linear embedding (over any Abelian group), then is it necessarily the case that
$$|\mathbb{E}_{(x_1, x_2, \ldots, x_k)\sim \mu^{\otimes n}}[f_1(x_1)f_2(x_2)\cdots f_k(x_k)] = o_{d, \delta}(1),$$
where the right hand side $\to 0$ as the degree $d \to \infty$ and $\delta \to 0$?
In this paper, we answer this analytical question fully and in the affirmative for $k=3$. We also show the following two applications of the result.
1. The first application is related to hardness of approximation. Using the reduction from [Bhangale-Khot-Minzer, STOC 2022], we show that for every $3$-ary predicate $P:\Sigma^3 \to \{0,1\}$ such that $P$ has no linear embedding, an SDP integrality gap instance of a $P$-CSP instance with gap $(1,s)$ can be translated into a dictatorship test with completeness $1$ and soundness $s+o(1)$, under certain additional conditions on the instance.
2. The second application is related to additive combinatorics. We show that if the distribution $\mu$ on $\Sigma^3$ has no linear embedding, marginals of $\mu$ are uniform on $\Sigma$, and $(a,a,a)\in supp(\mu)$ for every $a\in \Sigma$, then every large enough subset of $\Sigma^n$ contains a triple $(x_1, x_2,x_3)$ from $\mu^{\otimes n}$ (and in fact a significant density of such triples).Fri, 21 Apr 2023 01:00:35 +0300https://eccc.weizmann.ac.il/report/2023/055