Parallel Repetition of Free Entangled Games: Simplification and Improvements

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 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)}$.
Type de document :
Pré-publication, Document de travail
17 pages, this paper is a follow up and supersedes our previous paper 'Parallel Repetition of Ent.. 2014
Liste complète des métadonnées

Littérature citée [19 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01094123
Contributeur : André Chailloux <>
Soumis le : jeudi 11 décembre 2014 - 16:36:39
Dernière modification le : vendredi 25 mai 2018 - 12:02:05
Document(s) archivé(s) le : jeudi 12 mars 2015 - 11:00:58

Fichier

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

Identifiants

  • HAL Id : hal-01094123, version 1
  • ARXIV : 1410.4397

Collections

Citation

André Chailloux, Giannicola Scarpa. Parallel Repetition of Free Entangled Games: Simplification and Improvements. 17 pages, this paper is a follow up and supersedes our previous paper 'Parallel Repetition of Ent.. 2014. 〈hal-01094123〉

Partager

Métriques

Consultations de la notice

115

Téléchargements de fichiers

83