On Approximability of Satisfiable $k$-CSPs: VII
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912130714828800 |
|---|---|
| author | Bhangale, Amey Khot, Subhash Liu, Yang P. Minzer, Dor |
| author_facet | Bhangale, Amey Khot, Subhash Liu, Yang P. Minzer, Dor |
| contents | Let $Σ_1,\ldots,Σ_k$ be finite alphabets, and let $μ$ be a distribution over $Σ_1 \times \dots \times Σ_k$ in which the probability of each atom is at least $α$. We prove that if $μ$ does not admit Abelian embeddings, and $f_i: Σ_i \to \mathbb{C}$ are $1$-bounded functions (for $i=1,\ldots,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\colon Σ_1^n\to\mathbb{C}$ of degree at most $d$ and $\|L\|_2\leq 1$ such that $|\langle f_1, L\rangle|\geq δ$, where $d$ and $δ>0$ depend only on $k, α$ and $\varepsilon$. 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_15136 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On Approximability of Satisfiable $k$-CSPs: VII Bhangale, Amey Khot, Subhash Liu, Yang P. Minzer, Dor Computational Complexity Combinatorics Let $Σ_1,\ldots,Σ_k$ be finite alphabets, and let $μ$ be a distribution over $Σ_1 \times \dots \times Σ_k$ in which the probability of each atom is at least $α$. We prove that if $μ$ does not admit Abelian embeddings, and $f_i: Σ_i \to \mathbb{C}$ are $1$-bounded functions (for $i=1,\ldots,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\colon Σ_1^n\to\mathbb{C}$ of degree at most $d$ and $\|L\|_2\leq 1$ such that $|\langle f_1, L\rangle|\geq δ$, where $d$ and $δ>0$ depend only on $k, α$ and $\varepsilon$. 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. |
| title | On Approximability of Satisfiable $k$-CSPs: VII |
| topic | Computational Complexity Combinatorics |
| url | https://arxiv.org/abs/2411.15136 |