Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-199 | 16th August 2026 08:19

Parallel Repetition for Entangled Games with Gap Exponent Three

RSS-Feed




TR26-199
Authors: Zhao Song
Publication: 20th September 2026 17:48
Downloads: 46
Keywords: 


Abstract:

We prove that every finite two-player game $G$ with entangled value $\omega^*(G)=1-\epsilon$ satisfies
\[
\omega^*(G^{\otimes n})
\le\exp(-\Omega(\frac{\epsilon^3}{\epsilon+ \ell }n))
\]
for every $n\ge1$, where $\ell:=\log(|A| |B|)$, and $A$ and $B$ are the answer alphabets. Compared with Chapter 6 of the OpenAI report [Ope26], this improves the gap exponent from thirteen to three and matches the cubic gap dependence in Holenstein's general classical bound [Hol09]:
\[
\omega(G^{\otimes n})\le\exp(-\Omega( \frac{ (1-\omega(G))^3}{1+\ell} n)).
\]
The proof replaces the randomly shifted logarithmic grid used in quantum correlated sampling by smooth soft labels. This makes the relevant label infidelity quadratic in the distance between state descriptions and avoids a Jensen loss when averaging over questions. Together with the postselection argument, these improvements yield the cubic gap dependence stated above.



ISSN 1433-8092 | Imprint