Non-Signaling Parallel Repetition Using de Finetti Reductions

DOI10.1109/TIT.2016.2516022MaRDI QIDQ2976980zbMATH OpenDBLPWikidataFDO

Authors Rotem Arnon-Friedman, R. Renner, Thomas Vidick

Publication date 28 April 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1411.1582

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: In the context of multiplayer games, the parallel repetition problem can be phrased as follows: given a game $G$ with optimal winning probability $1-alpha$ and its repeated version $G^n$ (in which $n$ games are played together, in parallel), can the players use strategies that are substantially better than ones in which each game is played independently? This question is relevant in physics for the study of correlations and plays an important role in computer science in the context of complexity and cryptography. In this work the case of multiplayer non-signalling games is considered, i.e., the only restriction on the players is that they are not allowed to communicate during the game. For complete-support games (games where all possible combinations of questions have non-zero probability to be asked) with any number of players we prove a threshold theorem stating that the probability that non-signalling players win more than a fraction $$ of the $n$ games is exponentially small in $$, for every $$. For games with incomplete support we derive a similar statement, for a slightly modified form of repetition. The result is proved using a new technique, based on a recent de Finetti theorem, which allows us to avoid central technical difficulties that arise in standard proofs of parallel repetition theorems.

Cited in

(6)

• De Finetti theorems for the unitary dual group
• Belief-invariant and quantum equilibria in games of incomplete information
• Parallel Repetition of Computationally Sound Protocols Revisited
• Parallel repetition via fortification: analytic view and the quantum case
• DELEGATING COMPUTATION VIA NO-SIGNALING STRATEGIES
• De Finetti theorems for quantum conditional probability distributions with symmetry

This page was built for publication: Non-Signaling Parallel Repetition Using de Finetti Reductions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2976980)