Document Open Access Logo

Statistical Physics Approaches to Unique Games

Authors Matthew Coulson, Ewan Davies , Alexandra Kolla, Viresh Patel, Guus Regts

PDF
Thumbnail PDF

File

LIPIcs.CCC.2020.13.pdf
  • Filesize: 0.61 MB
  • 27 pages

Document Identifiers

Author Details

Matthew Coulson
  • Department of Mathematics, Universitat Politècnica de Catalunya, Barcelona, Spain
Ewan Davies
  • Department of Computer Science, University of Colorado, Boulder, CO, USA
Alexandra Kolla
  • Department of Computer Science, University of Colorado, Boulder, CO, USA
Viresh Patel
  • Korteweg-de Vries Institute for Mathematics, University of Amsterdam, The Netherlands
Guus Regts
  • Korteweg-de Vries Institute for Mathematics, University of Amsterdam, The Netherlands

Funding

Part of this work was done while E. Davies, A. Kolla, and G. Regts were visiting the Simons Institute for the Theory of Computing. Part of this work was done while M. Coulson was visiting V. Patel and G. Regts at the University of Amsterdam.
  • Coulson, Matthew: Visit to the University of Amsterdam funded by a Universitas 21 Travel Grant from the University of Birmingham. Supported by the Spanish Ministerio de Economía y Competitividad project MTM2017 - 82166 - P and an FPI Predoctoral Fellowship from the Spanish Ministerio de Economía y Competitividad with reference PRE2018 - 083621.
  • Kolla, Alexandra: Partially supported by NSF Career award 1452923.
  • Patel, Viresh: Partially supported by the Netherlands Organisation for Scientific Research (NWO) through Gravitation-grant NETWORKS-024.002.003.

Acknowledgements

We would like to thank Tyler Helmuth for insightful discussions, and the anonymous referees for comments.

Cite AsGet BibTex

Matthew Coulson, Ewan Davies, Alexandra Kolla, Viresh Patel, and Guus Regts. Statistical Physics Approaches to Unique Games. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 13:1-13:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.CCC.2020.13

Abstract

We show how two techniques from statistical physics can be adapted to solve a variant of the notorious Unique Games problem, potentially opening new avenues towards the Unique Games Conjecture. The variant, which we call Count Unique Games, is a promise problem in which the "yes" case guarantees a certain number of highly satisfiable assignments to the Unique Games instance. In the standard Unique Games problem, the "yes" case only guarantees at least one such assignment. We exhibit efficient algorithms for Count Unique Games based on approximating a suitable partition function for the Unique Games instance via (i) a zero-free region and polynomial interpolation, and (ii) the cluster expansion. We also show that a modest improvement to the parameters for which we give results would be strong negative evidence for the truth of the Unique Games Conjecture.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Approximation algorithms
  • Theory of computation → Approximation algorithms analysis
  • Theory of computation → Algorithm design techniques
Keywords
  • Unique Games Conjecture
  • approximation algorithm
  • Potts model
  • cluster expansion
  • polynomial interpolation

Metrics

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

Related Versions

References

  1. Sanjeev Arora, Boaz Barak, and David Steurer. Subexponential algorithms for unique games and related problems. In FOCS, pages 563-572. IEEE Computer Society, 2010. URL: https://doi.org/10.1109/FOCS.2010.59.
  2. Sanjeev Arora, Russell Impagliazzo, William Matthews, and David Steurer. Improved algorithms for unique games via divide and conquer. Electronic Colloquium on Computational Complexity (ECCC), 17:41, 2010. URL: https://eccc.weizmann.ac.il/report/2010/041/.
  3. Sanjeev Arora, Subhash Khot, Alexandra Kolla, David Steurer, Madhur Tulsiani, and Nisheeth K. Vishnoi. Unique games on expanding constraint graphs are easy: extended abstract. In STOC, pages 21-28. ACM, 2008. URL: https://doi.org/10.1145/1374376.1374380.
  4. Alexander Barvinok. Combinatorics and complexity of partition functions. Algorithms and Combinatorics, 2016. URL: https://doi.org/10.1007/978-3-319-51829-9.
  5. Alexander Barvinok. Approximating real-rooted and stable polynomials, with combinatorial applications. Online Journal of Analytic Combintaorics, 14, 2019. URL: https://web.math.rochester.edu/misc/ojac/vol14/186.pdf.
  6. Ferenc Bencs, Ewan Davies, Viresh Patel, and Guus Regts. On zero-free regions for the anti-ferromagnetic Potts model on bounded-degree graphs. arXiv preprint, 2018. URL: http://arxiv.org/abs/1812.07532.
  7. Magnus Bordewich, Catherine S. Greenhill, and Viresh Patel. Mixing of the Glauber dynamics for the ferromagnetic Potts model. Random Struct. Algorithms, 48(1):21-52, 2016. URL: https://doi.org/10.1002/RSA.20569.
  8. Christian Borgs, Jennifer Chayes, Tyler Helmuth, Will Perkins, and Prasad Tetali. Efficient sampling and counting algorithms for the Potts model on ℤ_d at all temperatures. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2020), 2020. URL: https://doi.org/10.1145/3357713.3384271.
  9. Shuchi Chawla, Robert Krauthgamer, Ravi Kumar, Yuval Rabani, and D. Sivakumar. On the hardness of approximating multicut and sparsest-cut. In IEEE Conference on Computational Complexity, pages 144-153. IEEE Computer Society, 2005. URL: https://doi.org/10.1109/CCC.2005.20.
  10. R. M. Corless, G. H. Gonnet, D. E. G. Hare, D. J. Jeffrey, and D. E. Knuth. On the Lambert W function. Adv. Comput. Math., 5(4):329-359, 1996. URL: https://doi.org/10.1007/BF02124750.
  11. Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra. On non-optimally expanding sets in Grassmann graphs. In STOC, pages 940-951. ACM, 2018. URL: https://doi.org/10.1145/3188745.3188806.
  12. Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra. Towards a proof of the 2-to-1 games conjecture? In STOC, pages 376-389. ACM, 2018. URL: https://doi.org/10.1145/3188745.3188804.
  13. Uriel Feige and Gideon Schechtman. On the optimality of the random hyperplane rounding technique for MAX CUT. Random Struct. Algorithms, 20(3):403-440, 2002. URL: https://doi.org/10.1002/RSA.10036.
  14. Andreas Galanis, Daniel Stefankovic, Eric Vigoda, and Linji Yang. Ferromagnetic Potts model: Refined #BIS-hardness and related results. SIAM Journal on Computing, 45(6):2004-2065, 2016. URL: https://doi.org/10.1137/140997580.
  15. Michel X. Goemans and David P. Williamson. .879-approximation algorithms for MAX CUT and MAX 2SAT. In STOC, pages 422-431. ACM, 1994. URL: https://doi.org/10.1145/195058.195216.
  16. Olle Häggström. The random-cluster model on a homogeneous tree. Probability Theory and Related Fields, 104(2):231-253, 1996. URL: https://doi.org/10.1007/BF01247839.
  17. Tyler Helmuth, Will Perkins, and Guus Regts. Algorithmic Pirogov-Sinai theory. In STOC, pages 1009-1020. ACM, 2019. URL: https://doi.org/10.1145/3313276.3316305.
  18. Howard J. Karloff. How good is the Goemans-Williamson MAX CUT algorithm? In STOC, pages 427-434. ACM, 1996. URL: https://doi.org/10.1145/237814.237990.
  19. Subhash Khot. On the power of unique 2-prover 1-round games. In STOC, pages 767-775. ACM, 2002. URL: https://doi.org/10.1145/509907.510017.
  20. Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O'Donnell. Optimal Inapproximability Results for Max-Cut and Other 2-Variable CSPs? In FOCS, pages 146-154. IEEE Computer Society, 2004. URL: https://doi.org/10.1109/FOCS.2004.49.
  21. Subhash Khot and Oded Regev. Vertex Cover Might be Hard to Approximate to within 2-ε. In IEEE Conference on Computational Complexity, pages 379-386. IEEE Computer Society, 2003. URL: https://doi.org/10.1109/CCC.2003.1214437.
  22. Subhash Khot and Nisheeth K. Vishnoi. The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into 𝓁₁. In FOCS, pages 53-62. IEEE Computer Society, 2005. URL: https://doi.org/10.1109/SFCS.2005.74.
  23. Alexandra Kolla. Spectral algorithms for unique games. In IEEE Conference on Computational Complexity, pages 122-130. IEEE Computer Society, 2010. URL: https://doi.org/10.1109/CCC.2010.20.
  24. Jingcheng Liu, Alistair Sinclair, and Piyush Srivastava. A deterministic algorithm for counting colorings with 2Δ colors. In IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS 2019), 2019. URL: https://doi.org/10.1109/FOCS.2019.00085.
  25. Konstantin Makarychev and Yury Makarychev. How to play unique games on expanders. In WAOA, volume 6534 of Lecture Notes in Computer Science, pages 190-200. Springer, 2010. URL: https://doi.org/10.1007/978-3-642-18318-8_17.
  26. Viresh Patel and Guus Regts. Deterministic Polynomial-Time Approximation Algorithms for Partition Functions and Graph Polynomials. SIAM J. Comput., 46(6):1893-1919, 2017. URL: https://doi.org/10.1137/16M1101003.
  27. Viresh Patel and Guus Regts. Computing the number of induced copies of a fixed graph in a bounded degree graph. Algorithmica, 81(5):1844-1858, 2019. URL: https://doi.org/10.1007/S00453-018-0511-9.
  28. Han Peters and Guus Regts. Location of zeros for the partition function of the Ising model on bounded degree graphs. Journal of the London Mathematical Society, page jlms.12286, November 2019. URL: https://doi.org/10.1112/jlms.12286.
  29. Prasad Raghavendra. Optimal algorithms and inapproximability results for every CSP? In STOC, pages 245-254. ACM, 2008. URL: https://doi.org/10.1145/1374376.1374414.
  30. Prasad Raghavendra and David Steurer. Graph expansion and the unique games conjecture. In STOC, pages 755-764. ACM, 2010. URL: https://doi.org/10.1145/1806689.1806792.
  31. Rocco A. Servedio and Li-Yang Tan. Deterministic search for CNF satisfying assignments in almost polynomial time. In FOCS, pages 813-823. IEEE Computer Society, 2017. URL: https://doi.org/10.1109/FOCS.2017.80.
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