A Caltech Library Service

Parallel Repetition of Entangled Games

Kempe, Julia and Vidick, Thomas (2011) Parallel Repetition of Entangled Games. In: Proceedings of the 43rd annual ACM symposium on Theory of computing. ACM , New York, NY, pp. 353-362. ISBN 978-1-4503-0691-1.

PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


We consider one-round games between a classical referee and two players. One of the main questions in this area is the parallel repetition question: Is there a way to decrease the maximum winning probability of a game without increasing the number of rounds or the number of players? Classically, efforts to resolve this question, open for many years, have culminated in Raz’s celebrated parallel repetition theorem on one hand, and in efficient product testers for PCPs on the other. In the case where players share entanglement, the only previously known results are for special cases of games, and are based on techniques that seem inherently limited. Here we show for the first time that the maximum success probability of entangled games can be reduced through parallel repetition, provided it was not initially 1. Our proof is inspired by a seminal result of Feige and Kilian in the context of classical two-prover one-round interactive proofs. One of the main components in our proof is an orthogonalization lemma for operators, which might be of independent interest.

Item Type:Book Section
Related URLs:
URLURL TypeDescription DOIArticle Paper
Vidick, Thomas0000-0002-6405-365X
Additional Information:© 2011 ACM. We are indebted to Ryan O’Donnell for making publicly available his extremely clear and helpful lecture notes [24, 23] on Feige and Kilian’s parallel repetition result, and to user “ohai” of for pointing out the connection between the classical Procrustes problem and that of the robust orthonormalization of almost-orthogonal families of vectors. We would also like to thank Or Meir for an inspiring talk on classical product testers. We especially thank Oded Regev for useful discussions and helpful comments, and Tsuyoshi Ito and Ben Reichardt for comments. Supported by an Individual Research Grant of the Israeli Science Foundation, by European Research Council (ERC) Starting Grant QUCO and by the Wolfson Family Charitable Trust. Supported by ARO Grant W911NF-09-1-0440 and NSF Grant CCF-0905626. Part of this work was done while visiting LRI, University of Paris-Sud, Orsay, France.
Funding AgencyGrant Number
Israel Science FoundationUNSPECIFIED
European Research Council (ERC)UNSPECIFIED
Wolfson Family Charitable TrustUNSPECIFIED
Army Research Office (ARO)W911NF-09-1-0440
Record Number:CaltechAUTHORS:20140910-135518364
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:49554
Deposited By: Tony Diaz
Deposited On:10 Sep 2014 21:48
Last Modified:10 Nov 2021 18:45

Repository Staff Only: item control page