Document Open Access Logo

Parallel Repetition via Fortification: Analytic View and the Quantum Case

Authors Mohammad Bavarian, Thomas Vidick, Henry Yuen

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2017.22.pdf
  • Filesize: 0.69 MB
  • 33 pages

Document Identifiers

Author Details

Mohammad Bavarian
Thomas Vidick
Henry Yuen

Cite As Get BibTex

Mohammad Bavarian, Thomas Vidick, and Henry Yuen. Parallel Repetition via Fortification: Analytic View and the Quantum Case. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 22:1-22:33, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ITCS.2017.22

Abstract

In a recent work, Moshkovitz [FOCS'14] presented a transformation n two-player games called "fortification", and gave an elementary proof of an (exponential decay) parallel repetition theorem for fortified two-player projection games. In this paper, we give an analytic reformulation of Moshkovitz's fortification framework, which was originally cast in combinatorial terms. This reformulation allows us to expand the scope of the fortification method to new settings.

First, we show any game (not just projection games) can be fortified, and give a simple proof of parallel repetition for general fortified games. Then, we prove parallel repetition and fortification theorems for games with players sharing quantum entanglement, as well as games with more than two players. This gives a new gap amplification method for general games in the quantum and multiplayer settings, which has recently received much interest.

An important component of our work is a variant of the fortification transformation, called "ordered fortification", that preserves the entangled value of a game. The original fortification of Moshkovitz does not in general preserve the entangled value of a game, and this was a barrier to extending the fortification framework to the quantum setting.

Subject Classification

Keywords
  • Parallel repetition
  • quantum entanglement
  • non-local games

Metrics

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

References

  1. Rotem Arnon-Friedman, Renato Renner, and Thomas Vidick. Non-signalling parallel repetition using de finetti reductions. arXiv preprint arXiv:1411.1582, 2014. Google Scholar
  2. Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs: A new characterization of np. Journal of the ACM (JACM), 45(1):70-122, 1998. Google Scholar
  3. László Babai, Lance Fortnow, and Carsten Lund. Nondeterministic exponential time has two-prover interactive protocols. In Proceedings of Annual Symposium on Foundations of Computer Science (FOCS), pages 16-25, 1990. Google Scholar
  4. Mohammad Bavarian, Thomas Vidick, and Henry Yuen. Anchoring games for parallel repetition. arXiv preprint arXiv:1509.07466, 2015. Google Scholar
  5. Michael Ben-Or, Shafi Goldwasser, Joe Kilian, and Avi Wigderson. Multi-prover interactive proofs: How to remove intractability assumptions. In Proceedings of Symposium on Theory of computing (STOC), 1988. Google Scholar
  6. Amey Bhangale, Ramprasad Saptharishi, Girish Varma, and Rakesh Venkat. On fortification of projection games. In RANDOM (arXiv:1504.05556), 2015. Google Scholar
  7. Yonatan Bilu and Nathan Linial. Lifts, discrepancy and nearly optimal spectral gap. Combinatorica, 26(5):495-519, 2006. Google Scholar
  8. Mark Braverman and Ankit Garg. Small value parallel repetition for general games. In Proceedings of the Annual ACM Symposium on Theory of Computing (STOC), pages 335-340, 2015. Google Scholar
  9. Harry Buhrman, Serge Fehr, and Christian Schaffner. On the parallel repetition of multi-player games: The no-signaling case. arXiv preprint arXiv:1312.7455, 2013. Google Scholar
  10. André Chailloux and Giannicola Scarpa. Parallel repetition of entangled games with exponential decay via the superposed information cost. In Proceeding of International Colloquium on Automata, Languages, and Programming (ICALP), pages 296-307, 2014. Google Scholar
  11. Kai-Min Chung, Xiaodi Wu, and Henry Yuen. Parallel repetition for entangled k-player games via fast quantum search. In Proceedings of Conference on Computational Complexity (CCC), page 512, 2015. Google Scholar
  12. John F Clauser, Michael A Horne, Abner Shimony, and Richard A Holt. Proposed experiment to test local hidden-variable theories. Physical Review Letters, 23(15):880-884, 1969. Google Scholar
  13. Richard Cleve, Peter Høyer, Benjamin Toner, and John Watrous. Consequences and limits of nonlocal strategies. In Proceedings Conference on Computational Complexity (CCC), pages 236-249, 2004. Google Scholar
  14. Irit Dinur. The PCP theorem by gap amplification. Journal of the ACM (JACM), 54(3):12, 2007. Google Scholar
  15. Irit Dinur and David Steurer. Analytical approach to parallel repetition. In Proceedings ofAnnual ACM Symposium on Theory of Computing (STOC), pages 624-633, 2014. Google Scholar
  16. Irit Dinur, David Steurer, and Thomas Vidick. A parallel repetition theorem for entangled projection games. In Proceedings of Conference on Computational Complexity (CCC), pages 197-208, 2014. Google Scholar
  17. Uriel Feige and Joe Kilian. Two-prover protocols - low error at affordable rates. SIAM Journal on Computing, 30(1):324-346, 2000. Google Scholar
  18. Uriel Feige, Guy Kindler, and Ryan O'Donnell. Understanding parallel repetition requires understanding foams. In Proceedings of Conference on Computational Complexity (CCC), pages 179-192, 2007. Google Scholar
  19. Uriel Feige and Oleg Verbitsky. Error reduction by parallel repetition: a negative result. Combinatorica, 22(4):461-478, 2002. Google Scholar
  20. Lance Fortnow, John Rompel, and Michael Sipser. On the power of multi-power interactive protocols. In Proceedings of Structure in Complexity Theory Conference (CCC), pages 156-161, 1988. Google Scholar
  21. Johan Håstad. Some optimal inapproximability results. Journal of the ACM (JACM), 48(4), 2001. Google Scholar
  22. Thomas Holenstein. Parallel repetition: simplifications and the no-signaling case. In Proceedings of Symposium on Theory of computing (STOC), pages 411-419, 2007. Google Scholar
  23. Tsuyoshi Ito and Thomas Vidick. A multi-prover interactive proof for NEXP sound against entangled provers. In Proceedings of Foundations of Computer Science (FOCS), pages 243-252, 2012. Google Scholar
  24. Rahul Jain, Attila Pereszlényi, and Penghui Yao. A parallel repetition theorem for entangled two-player one-round games under product distributions. In Proceedings of Conference on Computational Complexity (CCC), pages 209-216, 2014. Google Scholar
  25. Julia Kempe and Thomas Vidick. Parallel repetition of entangled games. In Proceedings of Symposium on Theory of computing (STOC), pages 353-362, 2011. Google Scholar
  26. Fuad Kittaneh. Inequalities for the schatten p-norm IV. Communications in Mathematical Physics, 106(4):581-585, 1986. Google Scholar
  27. Cécilia Lancien and Andreas Winter. Parallel repetition and concentration for (sub-) no-signalling games via a flexible constrained de finetti reduction. arXiv preprint arXiv:1506.07002, 2015. Google Scholar
  28. Dana Moshkovitz. Parallel repetition from fortification. In Annual Symposium on Foundations of Computer Science (FOCS), pages 414-423, 2014. Google Scholar
  29. Anup Rao. Parallel repetition in projection games and a concentration bound. SIAM Journal on Computing, 40(6):1871-1891, 2011. Google Scholar
  30. Ran Raz. A parallel repetition theorem. SIAM Journal on Computing, 27(3):763-803, 1998. Google Scholar
  31. Ran Raz. A counterexample to strong parallel repetition. SIAM Journal on Computing, 40(3):771-777, 2011. Google Scholar
  32. Thomas Vidick. Three-player entangled XOR games are NP-hard to approximate. In Proceedings of the Foundations of Computer Science (FOCS), pages 766-775, 2013. 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 About DROPS Imprint Privacy Contact