OctoInformBeta

Threshold repetition for entangled games

A finite two-player one-round game GG has nonempty finite question sets 𝒳,𝒴\mathcal X,\mathcal Y, nonempty finite answer sets 𝒜,ℬ\mathcal A,\mathcal B, a question distribution μ\mu on 𝒳×𝒴\mathcal X\times\mathcal Y, and an acceptance predicate V:𝒳×𝒴×𝒜×ℬ→{0,1}V:\mathcal X\times\mathcal Y\times\mathcal A\times\mathcal B\to\{0,1\}. A finite-dimensional entangled strategy consists of a shared bipartite state and a local POVM for each player’s question. The entangled value v=ω*(G)v=\omega^*(G) is the supremum of the success probability over all such strategies and all finite local dimensions. In kk repetitions, a joint strategy assigns a local POVM to each player’s entire question string, with the question pairs sampled independently from μ\mu. Let WkW_k denote the number of accepted coordinates. Write d=|𝒜||ℬ|d=|\mathcal A||\mathcal B|. All logarithms are natural. For an excess δ>0\delta>0, the threshold event is Wk≥⌈(v+δ)k⌉W_k\ge\lceil(v+\delta)k\rceil. Threshold parallel repetition asks whether its probability decays exponentially in kk uniformly over joint strategies.

Yuen proved polynomial decay for the probability of winning every coordinate in arbitrary finite two-player entangled games with value less than one. Song proved exponential decay for this event with cubic dependence on the gap from one.

For v<1v<1, 0<δ<1−v0<\delta<1-v and k≥1k\ge1, the preprint proves that the supremum of the threshold probability over finite-dimensional joint strategies is at most exp⁡(−cδ5k/(1+log⁡d))\exp(-c\delta^5k/(1+\log d)) for a universal constant c>0c>0. For each fixed question distribution μ\mu, it also proves an exponential threshold bound with a rate proportional to δ3\delta^3.

The Lean library EntangledGames proves a bound of this kind with a different rate. Its Theorem 1.1 assumes v<1v<1, 0<δ<1−v0<\delta<1-v and k≥1k\ge1. Its threshold bound is sup⁡Pr⁡[Wk≥⌈(v+δ)k⌉]≤exp⁡(−2−101δ13k/(1+log⁡d))\sup\Pr[W_k\ge\lceil(v+\delta)k\rceil]\le\exp(-2^{-101}\delta^{13}k/(1+\log d)), where the supremum ranges over finite-dimensional joint strategies: the rate has δ13\delta^{13} where the preprint’s has δ5\delta^5.

The results on these pages are those of the Lean library, each stated as the Lean library states it and linked to the Lean declaration behind it. Lean has checked every one of them, so the Lean library is the reference: where the preprint states a result differently, the statement on the page is the Lean library’s, and the preprint’s is given beside it. The preprint gives the results their order and their names.