Document Open Access Logo

On Rich 2-to-1 Games

Authors Mark Braverman, Subhash Khot, Dor Minzer

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2021.27.pdf
  • Filesize: 0.58 MB
  • 20 pages

Document Identifiers

Author Details

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
Dor Minzer
  • Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA, USA

Funding

  • Braverman, Mark: Research supported in part by the NSF Alan T. Waterman Award, Grant No. 1933331, a Packard Fellowship in Science and Engineering, and the Simons Collaboration on Algorithms and Geometry.
  • Khot, Subhash: Supported by the NSF Award CCF-1422159, the Simons Collaboration on Algorithms and Geometry, and the Simons Investigator Award.

Cite As Get BibTex

Mark Braverman, Subhash Khot, and Dor Minzer. On Rich 2-to-1 Games. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 27:1-27:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ITCS.2021.27

Abstract

We propose a variant of the 2-to-1 Games Conjecture that we call the Rich 2-to-1 Games Conjecture and show that it is equivalent to the Unique Games Conjecture. We are motivated by two considerations. Firstly, in light of the recent proof of the 2-to-1 Games Conjecture [Subhash Khot et al., 2017; Irit Dinur et al., 2018; Irit Dinur et al., 2018; Subhash Khot et al., 2018], we hope to understand how one might make further progress towards a proof of the Unique Games Conjecture. Secondly, the new variant along with perfect completeness in addition, might imply hardness of approximation results that necessarily require perfect completeness and (hence) are not implied by the Unique Games Conjecture.

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
Keywords
  • PCP
  • Unique-Games
  • Perfect Completeness

Metrics

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

Related Versions

References

  1. 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, 1998. Google Scholar
  2. Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs: A new characterization of NP. J. ACM, 45(1):70-122, 1998. Google Scholar
  3. Boaz Barak, Pravesh K. Kothari, and David Steurer. Small-set expansion in shortcode graph and the 2-to-2 conjecture. In 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, January 10-12, 2019, San Diego, California, USA, pages 9:1-9:12, 2019. Google Scholar
  4. Amey Bhangale, Subhash Khot, and Devanathan Thiruvenkatachari. An improved dictatorship test with perfect completeness. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2017, December 11-15, 2017, Kanpur, India, pages 15:1-15:23, 2017. Google Scholar
  5. Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra. On non-optimally expanding sets in grassmann graphs. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 940-951, 2018. Google Scholar
  6. Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra. Towards a proof of the 2-to-1 games conjecture? In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 376-389, 2018. Google Scholar
  7. Irit Dinur, Elchanan Mossel, and Oded Regev. Conditional hardness for approximate coloring. SIAM J. Comput., 39(3):843-873, 2009. Google Scholar
  8. Uriel Feige, Shafi Goldwasser, Laszlo Lovász, Shmuel Safra, and Mario Szegedy. Interactive proofs and the hardness of approximating cliques. J. ACM, 43(2):268-292, March 1996. Google Scholar
  9. Uriel Feige and László Lovász. Two-prover one-round proof systems: Their power and their problems (extended abstract). In Proceedings of the 24th Annual ACM Symposium on Theory of Computing, May 4-6, 1992, Victoria, British Columbia, Canada, pages 733-744, 1992. Google Scholar
  10. Yuval Filmus, Guy Kindler, Noam Lifshitz, and Dor Minzer. Hypercontractivity on the symmetric group. arXiv preprint, 2020. URL: http://arxiv.org/abs/2009.05503.
  11. Subhash Khot. On the power of unique 2-prover 1-round games. In Proceedings of the 17th Annual IEEE Conference on Computational Complexity, Montréal, Québec, Canada, May 21-24, 2002, page 25, 2002. Google Scholar
  12. Subhash Khot. Inapproximability of NP-complete problems, discrete fourier analysis, and geometry. In Proceedings of the International Congress of Mathematicians 2010, pages 2676-2697, 2010. Google Scholar
  13. Subhash Khot. On the unique games conjecture. In Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, Cambridge, Massachusetts, June 9-12, 2010, pages 99-121, 2010. Google Scholar
  14. Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O'Donnell. Optimal inapproximability results for max-cut and other 2-variable csps? SIAM J. Comput., 37(1):319-357, April 2007. Google Scholar
  15. Subhash Khot, Dor Minzer, Dana Moshkovitz, and Muli Safra. Small set expansion in the johnson graph. Electronic Colloquium on Computational Complexity (ECCC), 25:78, 2018. Google Scholar
  16. Subhash Khot, Dor Minzer, and Muli Safra. On independent sets, 2-to-2 games, and grassmann graphs. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 576-589, 2017. Google Scholar
  17. Subhash Khot, Dor Minzer, and Muli Safra. Pseudorandom sets in grassmann graph have near-perfect expansion. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 592-601, 2018. Google Scholar
  18. Subhash Khot and Oded Regev. Vertex cover might be hard to approximate to within 2-epsilon. J. Comput. Syst. Sci., 74(3):335-349, 2008. Google Scholar
  19. Subhash Khot and Muli Safra. A two-prover one-round game with strong soundness. Theory of Computing, 9(28):863-887, 2013. URL: https://doi.org/10.4086/toc.2013.v009a028.
  20. Ran Raz. A parallel repetition theorem. SIAM J. Comput., 27(3):763-803, June 1998. Google Scholar
  21. Suguru Tamaki and Yuichi Yoshida. A query efficient non-adaptive long code test with perfect completeness. Random Struct. Algorithms, 47(2):386-406, 2015. Google Scholar
  22. Luca Trevisan. On Khot’s unique games conjecture. Bulletin of the AMS, 49(1):91-111, 2012. 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