Improved Parallel Repetition for GHZ-Supported Games via Spreadness
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917263086452736 |
|---|---|
| author | Liu, Yang P. Lovett, Shachar Mittal, Kunal |
| author_facet | Liu, Yang P. Lovett, Shachar Mittal, Kunal |
| contents | We prove that for any 3-player game $\mathcal G$, whose query distribution has the same support as the GHZ game (i.e., all $x,y,z\in \{0,1\}$ satisfying $x+y+z=0\pmod{2}$), the value of the $n$-fold parallel repetition of $\mathcal G$ decays exponentially fast: \[ \text{val}(\mathcal G^{\otimes n}) \leq \exp(-n^c)\] for all sufficiently large $n$, where $c>0$ is an absolute constant.
We also prove a concentration bound for the parallel repetition of the GHZ game: For any constant $ε>0$, the probability that the players win at least a $\left(\frac{3}{4}+ε\right)$ fraction of the $n$ coordinates is at most $\exp(-n^c)$, where $c=c(ε)>0$ is a constant.
In both settings, our work exponentially improves upon the previous best known bounds which were only polynomially small, i.e., of the order $n^{-Ω(1)}$. Our key technical tool is the notion of \emph{algebraic spreadness} adapted from the breakthrough work of Kelley and Meka (FOCS '23) on sets free of 3-term progressions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_09290 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Improved Parallel Repetition for GHZ-Supported Games via Spreadness Liu, Yang P. Lovett, Shachar Mittal, Kunal Computational Complexity We prove that for any 3-player game $\mathcal G$, whose query distribution has the same support as the GHZ game (i.e., all $x,y,z\in \{0,1\}$ satisfying $x+y+z=0\pmod{2}$), the value of the $n$-fold parallel repetition of $\mathcal G$ decays exponentially fast: \[ \text{val}(\mathcal G^{\otimes n}) \leq \exp(-n^c)\] for all sufficiently large $n$, where $c>0$ is an absolute constant. We also prove a concentration bound for the parallel repetition of the GHZ game: For any constant $ε>0$, the probability that the players win at least a $\left(\frac{3}{4}+ε\right)$ fraction of the $n$ coordinates is at most $\exp(-n^c)$, where $c=c(ε)>0$ is a constant. In both settings, our work exponentially improves upon the previous best known bounds which were only polynomially small, i.e., of the order $n^{-Ω(1)}$. Our key technical tool is the notion of \emph{algebraic spreadness} adapted from the breakthrough work of Kelley and Meka (FOCS '23) on sets free of 3-term progressions. |
| title | Improved Parallel Repetition for GHZ-Supported Games via Spreadness |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2602.09290 |