Skip to Main content Skip to Navigation
Conference papers

Parallel Repetition of Entangled Games with Exponential Decay via the Superposed Information Cost

Abstract : In a two-player game, two cooperating but non communicating players, Alice and Bob, receive inputs taken from a probability distribution. Each of them produces an output and they win the game if they satisfy some predicate on their inputs/outputs. The entangled value $\omega^*(G)$ of a game $G$ is the maximum probability that Alice and Bob can win the game if they are allowed to share an entangled state prior to receiving their inputs. The $n$-fold parallel repetition $G^n$ of $G$ consists of $n$ instances of $G$ where the players receive all the inputs at the same time and produce all the outputs at the same time. They win $G^n$ if they win each instance of $G$. In this paper we show that for any game $G$ such that $\omega^*(G) = 1 - \varepsilon < 1$, $\omega^*(G^n)$ decreases exponentially in $n$. First, for any game $G$ on the uniform distribution, we show that $\omega^*(G^n) = (1 - \varepsilon^2)^{\Omega\left(\frac{n}{\log(|I||O|)} - |\log(\varepsilon)|\right)}$, where $|I|$ and $|O|$ are the sizes of the input and output sets. From this result, we show that for any entangled game $G$, $\omega^*(G^n) = (1 - {\varepsilon^2})^{\Omega(\frac{n}{Q^4 \log(Q \cdot|O|)} - |\log(\varepsilon/Q)|)}$ where $p$ is the input distribution of $G$ and $Q = \max(\lceil \frac{1}{\min_{xy: p_{xy} \neq 0}\{\sqrt{p_{xy}}\}}\rceil, |I|)$. To prove this parallel repetition, we introduce the concept of \emph{Superposed Information Cost} for entangled games which is inspired from the information cost used in communication complexity.
Complete list of metadata

Cited literature [26 references]  Display  Hide  Download

https://hal.inria.fr/hal-01094111
Contributor : André Chailloux Connect in order to contact the contributor
Submitted on : Monday, December 22, 2014 - 11:49:00 AM
Last modification on : Thursday, March 5, 2020 - 4:54:23 PM
Long-term archiving on: : Saturday, April 15, 2017 - 7:28:45 AM

File

1310.7787.pdf
Files produced by the author(s)

Identifiers

Collections

`

Citation

André Chailloux, Giannicola Scarpa. Parallel Repetition of Entangled Games with Exponential Decay via the Superposed Information Cost. ICALP 2014, Jun 2014, Copenhague, Denmark. pp.296 - 307, ⟨10.1007/978-3-662-43948-7_25⟩. ⟨hal-01094111⟩

Share

Metrics

Record views

265

Files downloads

248