A Caltech Library Service

Non-Signaling Parallel Repetition Using de Finetti Reductions

Arnon-Friedman, Rotem and Renner, Renato and Vidick, Thomas (2016) Non-Signaling Parallel Repetition Using de Finetti Reductions. IEEE Transactions on Information Theory, 62 (3). pp. 1440-1457. ISSN 0018-9448. doi:10.1109/TIT.2016.2516022.

[img] PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


In the context of multiplayer games, the parallel repetition problem can be phrased as follows: given a game G with optimal winning probability 1 - α 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 paper, the case of multiplayer non-signaling 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-signaling players win more than a fraction 1-α+β of the n games is exponentially small in nβ^2 for every 0 ≤ β ≤ α. 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.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper
Vidick, Thomas0000-0002-6405-365X
Additional Information:© 2016 IEEE. IEEE Open Access Publishing Agreement. Manuscript received May 5, 2015; revised September 18, 2015; accepted December 22, 2015. Date of publication January 8, 2016; date of current version February 12, 2016. R. Arnon-Friedman and R. Renner were supported in part by the European Research Council under Grant 258932, in part by the European Commission Strategic Targeted Research Project RAQUEL, in part by the Swiss National Science Foundation via the National Centre of Competence in Research through the QSIT Project, and in part by the CHIST-ERA Project DIQIP. T. Vidick was supported in part by the Simons Institute, Berkeley, CA, USA, in part by the Ministry of Education, Singapore, under the Tier 3 under Grant MOE2012-T3-1-009, and in part by the Perimeter Institute, Waterloo, ON, Canada. The authors would like to thank Anthony Leverrier, Yeong-Cherng Liang, and David Sutter for helpful discussions, and Christian Schaffner for pointing out a mistake in a preliminary version of this work, as well as to the anonymous referees for their helpful comments.
Funding AgencyGrant Number
European Research Council (ERC)258932
European Commission Strategic Targeted Research ProjectUNSPECIFIED
Swiss National Science Foundation (SNSF)UNSPECIFIED
European Coordinated Research on Long-term Challenges in Information and Communication Sciences & Technologies ERA-NET (CHIST-ERA)UNSPECIFIED
Simons InstituteUNSPECIFIED
Ministry of Education (Singapore)MOE2012-T3-1-009
Perimeter InstituteUNSPECIFIED
Subject Keywords:Parallel repetition, threshold theorem, multiplayer games, non-signalling players, de Finetti theorems, non-locality, correlations, probability theory, quantum entanglement
Issue or Number:3
Record Number:CaltechAUTHORS:20160318-101440389
Persistent URL:
Official Citation:R. Arnon-Friedman, R. Renner and T. Vidick, "Non-Signaling Parallel Repetition Using de Finetti Reductions," in IEEE Transactions on Information Theory, vol. 62, no. 3, pp. 1440-1457, March 2016. doi: 10.1109/TIT.2016.2516022
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:65478
Deposited By: Tony Diaz
Deposited On:18 Mar 2016 17:51
Last Modified:10 Nov 2021 23:46

Repository Staff Only: item control page