Nothing Special   »   [go: up one dir, main page]
Document Open Access Logo

Parallel Repetition of k-Player Projection Games

Authors Amey Bhangale , Mark Braverman , Subhash Khot , Yang P. Liu , Dor Minzer

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2024.54.pdf
  • Filesize: 0.77 MB
  • 16 pages

Document Identifiers

Author Details

Amey Bhangale
  • Department of Computer Science and Engineering, University of California, Riverside, CA, USA
Mark Braverman
  • Department of Computer Science, Princeton University, NJ, USA
Subhash Khot
  • Department of Computer Science, Courant Institute of Mathematical Sciences, New York University, NY, USA
Yang P. Liu
  • School of Mathematics, Institute for Advanced Study, Princeton, NJ, USA
Dor Minzer
  • Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA, USA

Funding

  • Bhangale, Amey: Supported by the Hellman Fellowship award.
  • Braverman, Mark: Supported by the National Science Foundation under the Alan T. Waterman Award, Grant No. 1933331.
  • Khot, Subhash: Supported by the NSF Award CCF-2130816 and the Simons Investigator Award.
  • Liu, Yang P.: Partially supported by NSF DMS-1926686.
  • Minzer, Dor: Supported by NSF CCF award 2227876 and NSF CAREER award 2239160.

Acknowledgements

We thank Kunal Mittal for helpful discussions at the early stage of this work. We also thank anonymous reviewers for helpful suggestions

Cite AsGet BibTex

Amey Bhangale, Mark Braverman, Subhash Khot, Yang P. Liu, and Dor Minzer. Parallel Repetition of k-Player Projection Games. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 54:1-54:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2024.54

Abstract

We study parallel repetition of k-player games where the constraints satisfy the projection property. We prove exponential decay in the value of a parallel repetition of projection games with a value less than 1.

Subject Classification

ACM Subject Classification
  • Theory of computation → Interactive proof systems
Keywords
  • Parallel Repetition
  • Multiplayer games
  • Projection games

Metrics

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

References

  1. Sanjeev Arora, László Babai, Jacques Stern, and Z. Sweedyk. The Hardness of Approximate Optima in Lattices, Codes, and Systems of Linear Equations. Journal of Computer and System Sciences, 54(2):317-331, April 1997. URL: https://doi.org/10.1006/jcss.1997.1472.
  2. Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. J. ACM, 45(3):501-555, May 1998. URL: https://doi.org/10.1145/278298.278306.
  3. Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs: a new characterization of np. J. ACM, 45(1):70-122, January 1998. URL: https://doi.org/10.1145/273865.273901.
  4. Mihir Bellare, Oded Goldreich, and Madhu Sudan. Free bits, pcps, and nonapproximability - Towards tight results. SIAM Journal on Computing, 27(3):804-915, 1998. URL: https://doi.org/10.1137/S0097539796302531.
  5. Amey Bhangale, Subhash Khot, and Dor Minzer. On Approximability of Satisfiable k-CSPs: II. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, pages 632-642, New York, NY, USA, 2023. Association for Computing Machinery. URL: https://doi.org/10.1145/3564246.3585120.
  6. Amey Bhangale, Swastik Kopparty, and Sushant Sachdeva. Simultaneous approximation of constraint satisfaction problems. In Automata, Languages, and Programming: 42nd International Colloquium, ICALP 2015, Kyoto, Japan, volume 9134, pages 193-205, 2015. URL: https://doi.org/10.1007/978-3-662-47672-7_16.
  7. Mark Braverman and Ankit Garg. Small value parallel repetition for general games. In Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, STOC '15, pages 335-340, New York, NY, USA, 2015. ACM. URL: https://doi.org/10.1145/2746539.2746565.
  8. Mark Braverman, Subhash Khot, and Dor Minzer. Parallel repetition for the ghz game: Exponential decay. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 1337-1341, 2023. URL: https://doi.org/10.1109/FOCS57990.2023.00080.
  9. Irit Dinur, Venkatesan Guruswami, Subhash Khot, and Oded Regev. A new multilayered pcp and the hardness of hypergraph vertex cover. SIAM Journal on Computing, 34(5):1129-1146, 2005. URL: https://doi.org/10.1137/S0097539704443057.
  10. Irit Dinur, Prahladh Harsha, Rakesh Venkat, and Henry Yuen. Multiplayer Parallel Repetition for Expanding Games. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017), volume 67, pages 37:1-37:16, Dagstuhl, Germany, 2017. URL: https://doi.org/10.4230/LIPIcs.ITCS.2017.37.
  11. Irit Dinur, Oded Regev, and Clifford Smyth. The hardness of 3-uniform hypergraph coloring. Combinatorica, 25(5):519-535, 2005. URL: https://doi.org/10.1007/s00493-005-0032-4.
  12. Irit Dinur and David Steurer. Analytical approach to parallel repetition. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 624-633, 2014. URL: https://doi.org/10.1145/2591796.2591884.
  13. Uriel Feige. A threshold of ln n for approximating set cover. J. ACM, 45(4):634-652, July 1998. URL: https://doi.org/10.1145/285055.285059.
  14. Uriel Feige, Shafi Goldwasser, Laszlo Lovász, Shmuel Safra, and Mario Szegedy. Interactive proofs and the hardness of approximating cliques. Journal of the ACM (JACM), 43(2):268-292, 1996. URL: https://doi.org/10.1145/226643.226652.
  15. H. Furstenberg and Y. Katznelson. A density version of the hales-jewett theorem for k=3. Discrete Mathematics, 75(1):227-241, 1989. URL: https://doi.org/10.1016/0012-365X(89)90089-7.
  16. 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), volume 207, pages 62:1-62:19, Dagstuhl, Germany, 2021. URL: https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.62.
  17. Uma Girish, Justin Holmgren, Kunal Mittal, Ran Raz, and Wei Zhan. Parallel repetition for all 3-player games over binary alphabet. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, pages 998-1009, New York, NY, USA, 2022. Association for Computing Machinery. URL: https://doi.org/10.1145/3519935.3520071.
  18. Uma Girish, Kunal Mittal, Ran Raz, and Wei Zhan. Polynomial Bounds on Parallel Repetition for All 3-Player Games with Binary Inputs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022), volume 245, pages 6:1-6:17, Dagstuhl, Germany, 2022. URL: https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2022.6.
  19. Daniel M. Greenberger, Michael A. Horne, and Anton Zeilinger. Going beyond bell’s theorem. In Menas Kafatos, editor, Bell’s Theorem, Quantum Theory and Conceptions of the Universe, pages 69-72. Springer Netherlands, Dordrecht, 1989. URL: https://doi.org/10.1007/978-94-017-0849-4_10.
  20. Venkatesan Guruswami, Johan Hastad, and Madhu Sudan. Hardness of approximate hypergraph coloring. SIAM Journal on Computing, 31(6):1663-1686, 2002. URL: https://doi.org/10.1137/S0097539700377165.
  21. Thomas Holenstein. Parallel Repetition: Simplification and the No-Signaling Case. Theory of Computing, 5(1):141-172, 2009. URL: https://doi.org/10.4086/toc.2009.v005a008.
  22. Justin Holmgren and Ran Raz. A parallel repetition theorem for the GHZ game. arXiv preprint arXiv:2008.05059, 2020. Google Scholar
  23. Johan Håstad. Some optimal inapproximability results. J. ACM, 48(4):798-859, July 2001. URL: https://doi.org/10.1145/502090.502098.
  24. S. Khot. Hardness results for coloring 3-colorable 3-uniform hypergraphs. In The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings., pages 23-32, 2002. URL: https://doi.org/10.1109/SFCS.2002.1181879.
  25. Subhash Khot. Hardness results for approximate hypergraph coloring. In Proceedings of the Thiry-Fourth Annual ACM Symposium on Theory of Computing, STOC '02, pages 351-359, New York, NY, USA, 2002. Association for Computing Machinery. URL: https://doi.org/10.1145/509907.509962.
  26. Kunal Mittal and Ran Raz. Block Rigidity: Strong Multiplayer Parallel Repetition Implies Super-Linear Lower Bounds for Turing Machines. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021), volume 185, pages 71:1-71:15, Dagstuhl, Germany, 2021. URL: https://doi.org/10.4230/LIPIcs.ITCS.2021.71.
  27. DHJ Polymath. A new proof of the density Hales-Jewett theorem. Annals of Mathematics, pages 1283-1327, 2012. URL: https://doi.org/10.4007/annals.2012.175.3.6.
  28. Anup Rao. Parallel Repetition in Projection Games and a Concentration Bound. SIAM Journal on Computing, 40(6):1871-1891, 2011. URL: https://doi.org/10.1137/080734042.
  29. Ran Raz. A parallel repetition theorem. SIAM Journal on Computing, 27(3):763-803, 1998. URL: https://doi.org/10.1137/S0097539795280895.
  30. Oleg Verbitsky. Towards the Parallel Repetition Conjecture. Theor. Comput. Sci., 157(2):277-282, May 1996. URL: https://doi.org/10.1016/0304-3975(95)00165-4.
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