Skip to Main content Skip to Navigation
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 metadatas

Cited literature [19 references]  Display  Hide  Download

https://hal.inria.fr/hal-01094123
Contributor : André Chailloux <>
Submitted on : Thursday, December 11, 2014 - 4:36:39 PM
Last modification on : Thursday, March 5, 2020 - 4:53:37 PM
Long-term archiving on: : Thursday, March 12, 2015 - 11:00:58 AM

File

1410.4397.pdf
Files produced by the author(s)

Identifiers

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

Collections

Citation

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

Share

Metrics

Record views

146

Files downloads

102