Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR23-055 | 17th July 2023 15:49

On Approximability of Satisfiable $k$-CSPs: II

RSS-Feed




Revision #1
Authors: Amey Bhangale, Subhash Khot, Dor Minzer
Accepted on: 17th July 2023 15:49
Downloads: 129
Keywords: 


Abstract:

Let $\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).



Changes to previous version:

Fixed a minor error in the proof of Claim 6.9.


Paper:

TR23-055 | 20th April 2023 20:52

On Approximability of Satisfiable $k$-CSPs: II





TR23-055
Authors: Amey Bhangale, Subhash Khot, Dor Minzer
Publication: 21st April 2023 01:00
Downloads: 300
Keywords: 


Abstract:

Let $\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).



ISSN 1433-8092 | Imprint