# 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.
Type de document :
Communication dans un congrès
ICALP 2014, Jun 2014, Copenhague, Denmark. pp.296 - 307, 2014, 〈10.1007/978-3-662-43948-7_25〉
Domaine :

Littérature citée [26 références]

https://hal.inria.fr/hal-01094111
Contributeur : André Chailloux <>
Soumis le : lundi 22 décembre 2014 - 11:49:00
Dernière modification le : mardi 17 avril 2018 - 11:24:12
Document(s) archivé(s) le : samedi 15 avril 2017 - 07:28:45

### Fichier

1310.7787.pdf
Fichiers produits par l'(les) auteur(s)

### 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, 2014, 〈10.1007/978-3-662-43948-7_25〉. 〈hal-01094111〉

### Métriques

Consultations de la notice

## 135

Téléchargements de fichiers