Parallel Repetition of Free Entangled Games: Simplification and Improvements - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2014

Parallel Repetition of Free Entangled Games: Simplification and Improvements

Résumé

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 Alice and Bob receive all the inputs at the same time and must produce all the outputs at the same time. They win $G^n$ if they win each instance of $G$. Recently, there has been a series of works showing parallel repetition with exponential decay for projection games \cite{DSV13}, games on the uniform distribution \cite{CS14} and for free games, \emph{i.e.}, games on a product distribution \cite{JPY13}. This article is meant to be a follow up of \cite{CS14}, where we improve and simplify several parts of our previous paper. Our main result is that for any free game $G$ with value $\omega^*(G)=1-\eps$, we have $\omega^*(G^n) \le (1 - \eps^2)^{\Omega(\frac{n}{\log(l)})}$ where $l$ is the size of the output set of the game. This result improves on both the results in \cite{JPY13} and \cite{CS14}. The framework we use can also be extended to free projection games. We show that for a free projection game $G$ with value $\omega^*(G)=1-\eps$, we have $\omega^*(G^n) \le (1 - \eps)^{\Omega(n)}$.
Fichier principal
Vignette du fichier
1410.4397.pdf (246.02 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01094123 , version 1 (11-12-2014)

Identifiants

Citer

André Chailloux, Giannicola Scarpa. Parallel Repetition of Free Entangled Games: Simplification and Improvements. 2014. ⟨hal-01094123⟩

Collections

INRIA INRIA2
90 Consultations
65 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More