Document Open Access Logo

Parallel Repetition for the GHZ Game: A Simpler Proof

Authors Uma Girish, Justin Holmgren, Kunal Mittal, Ran Raz, Wei Zhan

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2021.62.pdf
  • Filesize: 0.72 MB
  • 19 pages

Document Identifiers

Author Details

Uma Girish
  • Department of Computer Science, Princeton University, NJ, USA
Justin Holmgren
  • NTT Research, Sunnyvale, CA, USA
Kunal Mittal
  • Department of Computer Science, Princeton University, NJ, USA
Ran Raz
  • Department of Computer Science, Princeton University, NJ, USA
Wei Zhan
  • Department of Computer Science, Princeton University, NJ, USA

Funding

  • Girish, Uma: Simons Collaboration on Algorithms and Geometry, by a Simons Investigator Award and by the National Science Foundation grants No. CCF-1714779, CCF-2007462.
  • Mittal, Kunal: Simons Collaboration on Algorithms and Geometry, by a Simons Investigator Award and by the National Science Foundation grants No. CCF-1714779, CCF-2007462.
  • Raz, Ran: Simons Collaboration on Algorithms and Geometry, by a Simons Investigator Award and by the National Science Foundation grants No. CCF-1714779, CCF-2007462.
  • Zhan, Wei: Simons Collaboration on Algorithms and Geometry, by a Simons Investigator Award and by the National Science Foundation grants No. CCF-1714779, CCF-2007462.

Cite AsGet BibTex

Uma Girish, Justin Holmgren, Kunal Mittal, Ran Raz, and Wei Zhan. Parallel Repetition for the GHZ Game: A Simpler Proof. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 62:1-62:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.62

Abstract

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 [Holmgren and Raz, 2020]. 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 [Greenberger et al., 1989] 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 [Dinur et al., 2017] 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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Interactive proof systems
Keywords
  • Parallel Repetition
  • GHZ
  • Polynomial
  • Multi-player

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Noga Alon and Bo'az Klartag. Economical toric spines via Cheeger’s inequality. J. Topol. Anal., 1(2):101-111, 2009. Google Scholar
  2. Boaz Barak, Mark Braverman, Xi Chen, and Anup Rao. How to compress interactive communication. SIAM J. Comput., 42(3):1327-1363, 2013. (also in STOC 2010). Google Scholar
  3. Mihir Bellare, Oded Goldreich, and Madhu Sudan. Free bits, PCPs, and nonapproximability - towards tight results. SIAM J. Comput., 27(3):804-915, 1998. (also in FOCS 1995). Google Scholar
  4. Michael Ben-Or, Shafi Goldwasser, Joe Kilian, and Avi Wigderson. Multi-prover interactive proofs: How to remove intractability assumptions. In STOC, pages 113-131, 1988. Google Scholar
  5. Mark Braverman and Ankit Garg. Small value parallel repetition for general games. In STOC, pages 335-340, 2015. Google Scholar
  6. Richard Cleve, Peter Høyer, Benjamin Toner, and John Watrous. Consequences and limits of nonlocal strategies. In CCC, pages 236-249, 2004. Google Scholar
  7. Irit Dinur, Prahladh Harsha, Rakesh Venkat, and Henry Yuen. Multiplayer parallel repetition for expanding games. In ITCS, volume 67 of LIPIcs, pages Art. No. 37, 16, 2017. Google Scholar
  8. Irit Dinur and David Steurer. Analytical approach to parallel repetition. In STOC, pages 624-633, 2014. Google Scholar
  9. Uriel Feige. On the success probability of the two provers in one-round proof systems. In CCC, pages 116-123. IEEE Computer Society, 1991. Google Scholar
  10. Uriel Feige. A threshold of ln n for approximating set cover. J. ACM, 45(4):634-652, 1998. (also in STOC 1996). Google Scholar
  11. Uriel Feige, Guy Kindler, and Ryan O'Donnell. Understanding parallel repetition requires understanding foams. In CCC, pages 179-192, 2007. Google Scholar
  12. Uriel Feige and Oleg Verbitsky. Error reduction by parallel repetition - A negative result. Comb., 22(4):461-478, 2002. Google Scholar
  13. Lance Fortnow, John Rompel, and Michael Sipser. On the power of multi-power interactive protocols. In CCC, pages 156-161. IEEE Computer Society, 1988. Google Scholar
  14. Lance Jeremy Fortnow. Complexity-theoretic aspects of interactive proof systems. PhD thesis, MIT, 1989. Google Scholar
  15. Daniel M. Greenberger, Michael A. Horne, and Anton Zeilinger. Going Beyond Bell’s Theorem, pages 69-72. Springer Netherlands, Dordrecht, 1989. Google Scholar
  16. Johan Håstad. Some optimal inapproximability results. J. ACM, 48(4):798-859, 2001. (also in STOC 1997). Google Scholar
  17. Thomas Holenstein. Parallel repetition: simplifications and the no-signaling case. Theory Comput., 5:141-172, 2009. (also in STOC 2007). Google Scholar
  18. Justin Holmgren and Ran Raz. A parallel repetition theorem for the GHZ game. CoRR, abs/2008.05059, 2020. URL: https://arxiv.org/abs/2008.05059.
  19. Justin Holmgren and Lisa Yang. The parallel repetition of non-signaling games: counterexamples and dichotomy. In STOC, pages 185-192. ACM, 2019. Google Scholar
  20. Guy Kindler, Ryan O'Donnell, Anup Rao, and Avi Wigderson. Spherical cubes and rounding in high dimensions. In FOCS, pages 189-198, 2008. Google Scholar
  21. Kunal Mittal and Ran Raz. Block rigidity: Strong multiplayer parallel repetition implies super-linear lower bounds for turing machines. In ITCS, volume 185 of LIPIcs, pages 71:1-71:15, 2021. Google Scholar
  22. Itzhak Parnafes, Ran Raz, and Avi Wigderson. Direct product results and the GCD problem, in old and new communication models. In STOC, pages 363-372. 1997. Google Scholar
  23. Ran Raz. A parallel repetition theorem. SIAM J. Comput., 27(3):763-803, 1998. (also in STOC 1995). Google Scholar
  24. Ran Raz. Parallel repetition of two prover games. In CCC, pages 3-6. 2010. Google Scholar
  25. Ran Raz. A counterexample to strong parallel repetition. SIAM J. Comput., 40(3):771-777, 2011. Google Scholar
  26. Oleg Verbitsky. Towards the parallel repetition conjecture. In CCC, pages 304-307. IEEE Computer Society, 1994. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact