Skip to Main content Skip to Navigation
New interface
Preprints, Working Papers, ...

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)}$.
Document type :
Preprints, Working Papers, ...
Complete list of metadata

Cited literature [19 references]  Display  Hide  Download
Contributor : André Chailloux Connect in order to contact the contributor
Submitted on : Thursday, December 11, 2014 - 4:36:39 PM
Last modification on : Friday, January 21, 2022 - 3:16:03 AM
Long-term archiving on: : Thursday, March 12, 2015 - 11:00:58 AM


Files produced by the author(s)


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



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



Record views


Files downloads