TY - GEN

T1 - Parallel repetition for the GHZ game

T2 - 24th International Conference on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2021 and 25th International Conference on Randomization and Computation, RANDOM 2021

AU - Girish, Uma

AU - Holmgren, Justin

AU - Mittal, Kunal

AU - Raz, Ran

AU - Zhan, Wei

N1 - Funding Information:
Funding Uma Girish: Simons Collaboration on Algorithms and Geometry, by a Simons Investigator Award and by the National Science Foundation grants No. CCF-1714779, CCF-2007462. Kunal Mittal: Simons Collaboration on Algorithms and Geometry, by a Simons Investigator Award and by the National Science Foundation grants No. CCF-1714779, CCF-2007462. Ran Raz: Simons Collaboration on Algorithms and Geometry, by a Simons Investigator Award and by the National Science Foundation grants No. CCF-1714779, CCF-2007462. Wei Zhan: Simons Collaboration on Algorithms and Geometry, by a Simons Investigator Award and by the National Science Foundation grants No. CCF-1714779, CCF-2007462.
Publisher Copyright:
© Uma Girish, Justin Holmgren, Kunal Mittal, Ran Raz, and Wei Zhan; licensed under Creative Commons License CC-BY 4.0

PY - 2021/9/1

Y1 - 2021/9/1

N2 - We give a new proof of the fact that the parallel repetition of the (3-player) GHZ game reduces the value of the game to zero polynomially quickly. That is, we show that the value of the n-fold GHZ game is at most n−Ω(1). This was first established by Holmgren and Raz [18]. We present a new proof of this theorem that we believe to be simpler and more direct. Unlike most previous works on parallel repetition, our proof makes no use of information theory, and relies on the use of Fourier analysis. The GHZ game [15] has played a foundational role in the understanding of quantum information theory, due in part to the fact that quantum strategies can win the GHZ game with probability 1. It is possible that improved parallel repetition bounds may find applications in this setting. Recently, Dinur, Harsha, Venkat, and Yuen [7] highlighted the GHZ game as a simple three-player game, which is in some sense maximally far from the class of multi-player games whose behavior under parallel repetition is well understood. Dinur et al. conjectured that parallel repetition decreases the value of the GHZ game exponentially quickly, and speculated that progress on proving this would shed light on parallel repetition for general multi-player (multi-prover) games.

AB - We give a new proof of the fact that the parallel repetition of the (3-player) GHZ game reduces the value of the game to zero polynomially quickly. That is, we show that the value of the n-fold GHZ game is at most n−Ω(1). This was first established by Holmgren and Raz [18]. We present a new proof of this theorem that we believe to be simpler and more direct. Unlike most previous works on parallel repetition, our proof makes no use of information theory, and relies on the use of Fourier analysis. The GHZ game [15] has played a foundational role in the understanding of quantum information theory, due in part to the fact that quantum strategies can win the GHZ game with probability 1. It is possible that improved parallel repetition bounds may find applications in this setting. Recently, Dinur, Harsha, Venkat, and Yuen [7] highlighted the GHZ game as a simple three-player game, which is in some sense maximally far from the class of multi-player games whose behavior under parallel repetition is well understood. Dinur et al. conjectured that parallel repetition decreases the value of the GHZ game exponentially quickly, and speculated that progress on proving this would shed light on parallel repetition for general multi-player (multi-prover) games.

KW - GHZ

KW - Multi-player

KW - Parallel repetition

KW - Polynomial

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

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

U2 - 10.4230/LIPIcs-APPROX/RANDOM.2021.62

DO - 10.4230/LIPIcs-APPROX/RANDOM.2021.62

M3 - Conference contribution

AN - SCOPUS:85115633965

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2021

A2 - Wootters, Mary

A2 - Sanita, Laura

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

Y2 - 16 August 2021 through 18 August 2021

ER -