TY - GEN

T1 - Parallel repetition of entangled games

AU - Kempe, Julia

AU - Vidick, Thomas

N1 - Copyright:
Copyright 2011 Elsevier B.V., All rights reserved.

PY - 2011

Y1 - 2011

N2 - 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.

AB - 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.

KW - entangled games

KW - parallel repetition

UR - http://www.scopus.com/inward/record.url?scp=79959721269&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79959721269&partnerID=8YFLogxK

U2 - 10.1145/1993636.1993684

DO - 10.1145/1993636.1993684

M3 - Conference contribution

AN - SCOPUS:79959721269

SN - 9781450306911

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 353

EP - 362

BT - STOC'11 - Proceedings of the 43rd ACM Symposium on Theory of Computing

T2 - 43rd ACM Symposium on Theory of Computing, STOC'11

Y2 - 6 June 2011 through 8 June 2011

ER -