Document Open Access Logo

Reduction from Non-Unique Games to Boolean Unique Games

Authors Ronen Eldan, Dana Moshkovitz

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2022.64.pdf
  • Filesize: 0.85 MB
  • 25 pages

Document Identifiers

Author Details

Ronen Eldan
  • Department of Mathematics, Weizmann Institute of Science, Rehovot, Israel
Dana Moshkovitz
  • Department of Computer Science, University of Texas at Austin, TX, USA

Funding

  • Eldan, Ronen: Supported by a European Research Council Starting Grant (ERC StG) and by an Israel Science Foundation grant no. 715/16.
  • Moshkovitz, Dana: This material is based upon work supported by the National Science Foundation under grants number 1218547 and 1648712.

Acknowledgements

We are thankful to Subhash Khot and Bo'az Klartag for discussions. We are especially grateful to Bo'az for suggesting to use Schur’s Lemma which is key to the proof of Theorem 8

Cite AsGet BibTex

Ronen Eldan and Dana Moshkovitz. Reduction from Non-Unique Games to Boolean Unique Games. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 64:1-64:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ITCS.2022.64

Abstract

We reduce the problem of proving a "Boolean Unique Games Conjecture" (with gap 1-δ vs. 1-Cδ, for any C > 1, and sufficiently small δ > 0) to the problem of proving a PCP Theorem for a certain non-unique game. In a previous work, Khot and Moshkovitz suggested an inefficient candidate reduction (i.e., without a proof of soundness). The current work is the first to provide an efficient reduction along with a proof of soundness. The non-unique game we reduce from is similar to non-unique games for which PCP theorems are known. Our proof relies on a new concentration theorem for functions in Gaussian space that are restricted to a random hyperplane. We bound the typical Euclidean distance between the low degree part of the restriction of the function to the hyperplane and the restriction to the hyperplane of the low degree part of the function.

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
Keywords
  • Unique Games Conjecture
  • hyperplane encoding
  • concentration of measure
  • low degree testing

Metrics

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

Related Versions

References

  1. S. Arora, B. Barak, and D. Steurer. Subexponential algorithms for unique games and related problems. In Proc. 51st IEEE Symp. on Foundations of Computer Science, 2010. Google Scholar
  2. S. Arora, S. A. Khot, A. Kolla, D. Steurer, M. Tulsiani, and N. Vishnoi. Unique games on expanding constraint graphs are easy: extended abstract. In Proc. 40th ACM Symp. on Theory of Computing, pages 21-28, 2008. Google Scholar
  3. S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and the hardness of approximation problems. Journal of the ACM, 45(3):501-555, 1998. Google Scholar
  4. S. Arora and S. Safra. Probabilistic checking of proofs: a new characterization of NP. Journal of the ACM, 45(1):70-122, 1998. Google Scholar
  5. B. Barak, M. Hardt, I. Haviv, A. Rao, O. Regev, and D. Steurer. Rounding parallel repetitions of unique games. In Proc. 49th IEEE Symp. on Foundations of Computer Science, pages 374-383, 2008. Google Scholar
  6. B. Barak, P. Kothari, and D. Steurer. Small-set expansion in shortcode graph and the 2-to-2 conjecture. In ITCS'19, 2019. Google Scholar
  7. M. Blum, M. Luby, and R. Rubinfeld. Self-testing/correcting with applications to numerical problems. Journal of Computer and System Sciences, 47(3):549-595, 1993. Google Scholar
  8. A. Carbery and J. Wright. Distributional and l_q norm inequalities for polynomials over convex bodies in Rⁿ. Math. Res. Lett., 8(3):233-248, 2001. Google Scholar
  9. S. O. Chan. Approximation resistance from pairwise independent subgroups. In Proc. 45th ACM Symp. on Theory of Computing, pages 447-456, 2013. Google Scholar
  10. M. Charikar, K. Makarychev, and Y. Makarychev. Near-optimal algorithms for maximum constraint satisfaction problems. ACM Transactions on Algorithms, 5(3), 2009. Google Scholar
  11. E. Chlamtac, K. Makarychev, and Y. Makarychev. How to play unique games using embeddings. In Proc. 47th IEEE Symp. on Foundations of Computer Science, pages 687-696, 2006. Google Scholar
  12. I. Dinur, S. Khot, G. Kindler, D. Minzer, and S. Safra. On non-optimally expanding sets in grassmann graphs. In Proc. 50th ACM Symp. on Theory of Computing, 2018. Google Scholar
  13. I. Dinur, S. Khot, G. Kindler, D. Minzer, and S. Safra. Towards a proof of the 2-to-1 games conjecture? In Proc. 50th ACM Symp. on Theory of Computing, pages 376-389, 2018. Google Scholar
  14. R. Eldan. A two-sided estimate for the gaussian noise stability deficit. Invent. Math., 2014. Google Scholar
  15. R. Eldan and B. Klartag. Pointwise estimates for marginals of convex bodies. J. Functional Analysis, 254(8):2275-2293, 2008. Google Scholar
  16. M. X. Goemans and D. P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM, 42(6):1115-1145, 1995. Google Scholar
  17. A. Gupta and K. Talwar. Approximating unique games. In SODA, pages 99-106, 2006. Google Scholar
  18. J. Håstad. Some optimal inapproximability results. Journal of the ACM, 48(4):798-859, 2001. Google Scholar
  19. J. Håstad, S. Huang, R. Manokaran, R. O'Donnell, and J. Wright. Improved NP-inapproximability for 2-variable linear equations. Theory of Computing, 13(19):1-51, 2017. Google Scholar
  20. S. Khot. On the power of unique 2-prover 1-round games. In Proc. 34th ACM Symp. on Theory of Computing, pages 767-775, 2002. Google Scholar
  21. S. Khot. On the unique games conjecture (invited survey). In IEEE Conference on Computational Complexity, pages 99-121, 2010. Google Scholar
  22. S. Khot, G. Kindler, E. Mossel, and R. O'Donnell. Optimal inapproximability results for MAX-CUT and other two-variable CSPs? SIAM Journal on Computing, 37(1):319-357, 2007. Google Scholar
  23. S. Khot, D. Minzer, D. Moshkovitz, and S. Safra. Small set expansion in the johnson graph. Technical Report TR18-078, ECCC, 2018. Google Scholar
  24. S. Khot, D. Minzer, and S. Safra. On independent sets, 2-to-2 games, and grassmann graphs. In Proc. 49th ACM Symp. on Theory of Computing, pages 576-589, 2017. Google Scholar
  25. S. Khot, D. Minzer, and S. Safra. Pseudorandom sets in grassmann graph have near-perfect expansion. In Proc. 59th IEEE Symp. on Foundations of Computer Science, 2018. Google Scholar
  26. S. Khot and D. Moshkovitz. NP-hardness of approximately solving linear equations over reals. In Proc. 43rd ACM Symp. on Theory of Computing, pages 413-420, 2011. Google Scholar
  27. S. Khot and D. Moshkovitz. Candidate hard unique game. In Proc. 48th ACM Symp. on Theory of Computing, pages 63-76, 2016. Google Scholar
  28. S. Khot and O. Regev. Vertex cover might be hard to approximate to within 2-epsilon. Journal of Computer and System Sciences, 74(3):335-349, 2008. Google Scholar
  29. B. Klartag and O. Regev. Quantum one-way communication can be exponentially stronger than classical communication. In Proc. 43rd ACM Symp. on Theory of Computing, pages 31-40, 2011. Google Scholar
  30. A. Kolla, K. Makarychev, and Y. Makarychev. How to play unique games against a semi-random adversary: Study of semi-random models of unique games. In Proc. 52nd IEEE Symp. on Foundations of Computer Science, pages 443-452, 2011. Google Scholar
  31. P. McCullagh. Tensor methods in statistics. Monographs on Statistics and Applied Probability. Chapman & Hall, London, 1987. Google Scholar
  32. D. Moshkovitz and R. Raz. Two query PCP with sub-constant error. Journal of the ACM, 57(5), 2010. Google Scholar
  33. E. Mossel and J. Neeman. Robust dimension free isoperimetry in gaussian space. Annals of Probability, 43(3):971-991, 2015. Google Scholar
  34. E. Mossel and J. Neeman. Robust optimality of gaussian noise stability. Journal of the European Math Society (JEMS), 17(2):433-482, 2015. Google Scholar
  35. E. Mossel and J. Neeman. Noise stability and correlation with half spaces. Electron. J. Probab., 23(16), 2018. Google Scholar
  36. R. O'Donnell. Analysis of Boolean Functions. Cambridge University Press, 2014. Google Scholar
  37. P. Raghavendra. Optimal algorithms and inapproximability results for every csp? In Proc. 40th ACM Symp. on Theory of Computing, pages 245-254, 2008. Google Scholar
  38. R. Raz. A parallel repetition theorem. In SIAM Journal on Computing, volume 27, pages 763-803, 1998. Google Scholar
  39. R. Raz. A counterexample to strong parallel repetition. SIAM Journal on Computing, 40(3):771-777, 2011. Google Scholar
  40. R. Rubinfeld and M. Sudan. Robust characterizations of polynomials with applications to program testing. SIAM Journal on Computing, 25(2):252-271, 1996. Google Scholar
  41. L. Trevisan. Approximation algorithms for unique games. Theory of Computing, 4(1):111-128, 2008. 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