Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Parallel repetition of entangled games
 
conference paper

Parallel repetition of entangled games

Kempe, Julia
•
Vidick, Thomas  orcid-logo
2011
STOC '11: Proceedings of the forty-third annual ACM symposium on Theory of computing
43rd ACM Symposium on Theory of Computing

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. © 2011 ACM.

  • Details
  • Metrics
Type
conference paper
DOI
10.1145/1993636.1993684
Scopus ID

2-s2.0-79959721269

Author(s)
Kempe, Julia

Institut de Recherche en Informatique Fondamentale (IRIF)

Vidick, Thomas  orcid-logo

California Institute of Technology

Date Issued

2011

Publisher

Association for Computing Machinery

Published in
STOC '11: Proceedings of the forty-third annual ACM symposium on Theory of computing
ISBN of the book

9781450306911

Start page

353

End page

362

Subjects

entangled games

•

parallel repetition

Editorial or Peer reviewed

REVIEWED

Written at

OTHER

EPFL units
Non-EPFL  
Event nameEvent acronymEvent placeEvent date
43rd ACM Symposium on Theory of Computing

San Jose, United States

2011-06-06 - 2011-06-08

Available on Infoscience
November 25, 2025
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/256346
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés