Parallel Repetition for $3$-Player XOR Games
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866929463333224448 |
|---|---|
| author | Bhangale, Amey Braverman, Mark Khot, Subhash Liu, Yang P. Minzer, Dor |
| author_facet | Bhangale, Amey Braverman, Mark Khot, Subhash Liu, Yang P. Minzer, Dor |
| contents | In a $3$-$\mathsf{XOR}$ game $\mathcal{G}$, the verifier samples a challenge $(x,y,z)\sim μ$ where $μ$ is a probability distribution over $Σ\timesΓ\timesΦ$, and a map $t\colon Σ\timesΓ\timesΦ\to\mathcal{A}$ for a finite Abelian group $\mathcal{A}$ defining a constraint. The verifier sends the questions $x$, $y$ and $z$ to the players Alice, Bob and Charlie respectively, receives answers $f(x)$, $g(y)$ and $h(z)$ that are elements in $\mathcal{A}$ and accepts if $f(x)+g(y)+h(z) = t(x,y,z)$. The value, $\mathsf{val}(\mathcal{G})$, of the game is defined to be the maximum probability the verifier accepts over all players' strategies.
We show that if $\mathcal{G}$ is a $3$-$\mathsf{XOR}$ game with value strictly less than $1$, whose underlying distribution over questions $μ$ does not admit Abelian embeddings into $(\mathbb{Z},+)$, then the value of the $n$-fold repetition of $\mathcal{G}$ is exponentially decaying. That is, there exists $c=c(\mathcal{G})>0$ such that $\mathsf{val}(\mathcal{G}^{\otimes n})\leq 2^{-cn}$. This extends a previous result of [Braverman-Khot-Minzer, FOCS 2023] showing exponential decay for the GHZ game. Our proof combines tools from additive combinatorics and tools from discrete Fourier analysis. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_09352 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Parallel Repetition for $3$-Player XOR Games Bhangale, Amey Braverman, Mark Khot, Subhash Liu, Yang P. Minzer, Dor Computational Complexity Discrete Mathematics In a $3$-$\mathsf{XOR}$ game $\mathcal{G}$, the verifier samples a challenge $(x,y,z)\sim μ$ where $μ$ is a probability distribution over $Σ\timesΓ\timesΦ$, and a map $t\colon Σ\timesΓ\timesΦ\to\mathcal{A}$ for a finite Abelian group $\mathcal{A}$ defining a constraint. The verifier sends the questions $x$, $y$ and $z$ to the players Alice, Bob and Charlie respectively, receives answers $f(x)$, $g(y)$ and $h(z)$ that are elements in $\mathcal{A}$ and accepts if $f(x)+g(y)+h(z) = t(x,y,z)$. The value, $\mathsf{val}(\mathcal{G})$, of the game is defined to be the maximum probability the verifier accepts over all players' strategies. We show that if $\mathcal{G}$ is a $3$-$\mathsf{XOR}$ game with value strictly less than $1$, whose underlying distribution over questions $μ$ does not admit Abelian embeddings into $(\mathbb{Z},+)$, then the value of the $n$-fold repetition of $\mathcal{G}$ is exponentially decaying. That is, there exists $c=c(\mathcal{G})>0$ such that $\mathsf{val}(\mathcal{G}^{\otimes n})\leq 2^{-cn}$. This extends a previous result of [Braverman-Khot-Minzer, FOCS 2023] showing exponential decay for the GHZ game. Our proof combines tools from additive combinatorics and tools from discrete Fourier analysis. |
| title | Parallel Repetition for $3$-Player XOR Games |
| topic | Computational Complexity Discrete Mathematics |
| url | https://arxiv.org/abs/2408.09352 |