Document Open Access Logo

Random Max-CSPs Inherit Algorithmic Hardness from Spin Glasses

Authors Chris Jones , Kunal Marwaha , Juspreet Singh Sandhu , Jonathan Shi

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2023.77.pdf
  • Filesize: 0.97 MB
  • 26 pages

Document Identifiers

Author Details

Chris Jones
  • University of Chicago, Il, USA
Kunal Marwaha
  • University of Chicago, USA
Juspreet Singh Sandhu
  • Harvard University, Cambridge, MA, USA
Jonathan Shi
  • Bocconi University, Milano, Italy

Funding

  • Jones, Chris: Supported by the National Science Foundation under Grant No. CCF-2008920.
  • Marwaha, Kunal: Supported by the National Science Foundation Graduate Research Fellowship Program under Grant No. DGE-1746045.
  • Sandhu, Juspreet Singh: Supported by a Simons Investigator Fellowship, NSF grant DMS-2134157, NSF STAQ award PHY-1818914, DARPA grant W911NF2010021, DARPA ONISQ program award HR001120C0068 and DOE grant DE-SC0022199.
  • Shi, Jonathan: Supported by European Research Council (ERC) award No. 834861 (SO-ReCoDi).

Acknowledgements

We thank Antares Chen for collaborating during the early stages of this project. We also thank Peter J. Love for helpful feedback on a previous version of this manuscript. KM thanks Ryan Robinett for a tip on improving the numerical integration scheme. JSS did some of this work as a visiting student at Bocconi University. We thank the anonymous reviewers for many suggestions to improve the text, for pointing out an error in a proof, and for the reference [Barbier and Panchenko, 2022].

Cite As Get BibTex

Chris Jones, Kunal Marwaha, Juspreet Singh Sandhu, and Jonathan Shi. Random Max-CSPs Inherit Algorithmic Hardness from Spin Glasses. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 77:1-77:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ITCS.2023.77

Abstract

We study random constraint satisfaction problems (CSPs) at large clause density. We relate the structure of near-optimal solutions for any Boolean Max-CSP to that for an associated spin glass on the hypercube, using the Guerra-Toninelli interpolation from statistical physics. The noise stability polynomial of the CSP’s predicate is, up to a constant, the mixture polynomial of the associated spin glass. We show two main consequences:  
1) We prove that the maximum fraction of constraints that can be satisfied in a random Max-CSP at large clause density is determined by the ground state energy density of the corresponding spin glass. Since the latter value can be computed with the Parisi formula [Parisi, 1980; Talagrand, 2006; Auffinger and Chen, 2017], we provide numerical values for some popular CSPs. 
2) We prove that a Max-CSP at large clause density possesses generalized versions of the overlap gap property if and only if the same holds for the corresponding spin glass. We transfer results from [Huang and Sellke, 2021] to obstruct algorithms with overlap concentration on a large class of Max-CSPs. This immediately includes local classical and local quantum algorithms [Chou et al., 2022].

Subject Classification

ACM Subject Classification
  • Theory of computation → Randomness, geometry and discrete structures
  • Mathematics of computing → Probability and statistics
Keywords
  • spin glass
  • overlap gap property
  • constraint satisfaction problem
  • Guerra-Toninelli interpolation

Metrics

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

Related Versions

Supplementary Materials

References

  1. Dimitris Achlioptas and Amin Coja-Oghlan. Algorithmic barriers from phase transitions. In 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pages 793-802. IEEE, 2008. Google Scholar
  2. Dimitris Achlioptas and Cristopher Moore. The asymptotic order of the random k-sat threshold. In The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings., pages 779-788. IEEE, 2002. Google Scholar
  3. Dimitris Achlioptas and Federico Ricci-Tersenghi. On the solution-space geometry of random constraint satisfaction problems. In Proceedings of the thirty-eighth annual ACM Symposium on Theory of Computing, pages 130-139, 2006. Google Scholar
  4. Ahmed El Alaoui and Andrea Montanari. Algorithmic thresholds in mean field spin glasses. arXiv preprint, 2020. URL: http://arxiv.org/abs/2009.11481.
  5. Ahmed El Alaoui, Andrea Montanari, and Mark Sellke. Local algorithms for maximum cut and minimum bisection on locally treelike regular graphs of large degree. arXiv preprint, 2021. URL: http://arxiv.org/abs/2111.06813.
  6. Ahmed El Alaoui, Andrea Montanari, and Mark Sellke. Optimization of mean-field spin glasses. The Annals of Probability, 49(6), November 2021. URL: https://doi.org/10.1214/21-aop1519.
  7. Sarah R. Allen, Ryan O'Donnell, and David Witmer. How to refute a random csp. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 689-708, 2015. URL: https://doi.org/10.1109/FOCS.2015.48.
  8. Gérard Ben Arous, Alexander S Wein, and Ilias Zadik. Free energy wells and overlap gap property in sparse pca. In Conference on Learning Theory, pages 479-482. PMLR, 2020. Google Scholar
  9. Antonio Auffinger and Wei-Kuo Chen. Parisi formula for the ground state energy in the mixed p-spin model. The Annals of Probability, 45(6B):4617-4631, 2017. Google Scholar
  10. Antonio Auffinger, Wei-Kuo Chen, and Qiang Zeng. The sk model is infinite step replica symmetry breaking at zero temperature. Communications on Pure and Applied Mathematics, 73(5), 2020. Google Scholar
  11. Jean Barbier and Dmitry Panchenko. Strong replica symmetry in high-dimensional optimal bayesian inference. Communications in Mathematical Physics, pages 1-41, 2022. Google Scholar
  12. Joao Basso, Edward Farhi, Kunal Marwaha, Benjamin Villalonga, and Leo Zhou. The Quantum Approximate Optimization Algorithm at High Depth for MaxCut on Large-Girth Regular Graphs and the Sherrington-Kirkpatrick Model. In 17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022), pages 7:1-7:21, 2022. URL: https://doi.org/10.4230/LIPIcs.TQC.2022.7.
  13. Joao Basso, David Gamarnik, Song Mei, and Leo Zhou. Performance and limitations of the qaoa at constant levels on large sparse hypergraphs and spin glass models. FOCS 2022; arXiv:2204.10306, 2022. URL: http://arxiv.org/abs/2204.10306.
  14. Vijay Bhattiprolu, Venkatesan Guruswami, and Euiwoong Lee. Sum-of-Squares Certificates for Maxima of Random Tensors on the Sphere. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017), pages 31:1-31:20, 2017. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.31.
  15. Sami Boulebnane and Ashley Montanaro. Predicting parameters for the quantum approximate optimization algorithm for max-cut from the infinite-size limit. arXiv preprint, 2021. URL: http://arxiv.org/abs/2110.10685.
  16. Alfredo Braunstein, Marc Mézard, and Riccardo Zecchina. Survey propagation: An algorithm for satisfiability. Random Structures & Algorithms, 27(2):201-226, 2005. Google Scholar
  17. Guy Bresler and Brice Huang. The algorithmic phase transition of random k-sat for low degree polynomials. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 298-309. IEEE, 2022. Google Scholar
  18. Wei-Kuo Chen, David Gamarnik, Dmitry Panchenko, and Mustazee Rahman. Suboptimality of local algorithms for a class of max-cut problems. Annals of Probability, 47(3):1587-1618, 2019. Google Scholar
  19. Chi-Ning Chou, Peter J. Love, Juspreet Singh Sandhu, and Jonathan Shi. Limitations of Local Quantum Algorithms on Random MAX-k-XOR and Beyond. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), pages 41:1-41:20, 2022. URL: https://doi.org/10.4230/LIPIcs.ICALP.2022.41.
  20. Jahan Claes and Wim van Dam. Instance independence of single layer quantum approximate optimization algorithm on mixed-spin models at infinite size. Quantum, 5:542, September 2021. URL: https://doi.org/10.22331/q-2021-09-15-542.
  21. Andrea Crisanti and Tommaso Rizzo. Analysis of the ∞-replica symmetry breaking solution of the sherrington-kirkpatrick model. Physical Review E, 65(4), April 2002. URL: https://doi.org/10.1103/physreve.65.046137.
  22. Amir Dembo, Andrea Montanari, and Subhabrata Sen. Extremal cuts of sparse random graphs. The Annals of Probability, 45(2):1190-1217, 2017. Google Scholar
  23. Jian Ding, Allan Sly, and Nike Sun. Maximum independent sets on random regular graphs. Acta Mathematica, 217(2):263-340, 2016. Google Scholar
  24. Jian Ding, Allan Sly, and Nike Sun. Satisfiability threshold for random regular nae-sat. Communications in Mathematical Physics, 341(2):435-489, January 2016. URL: https://doi.org/10.1007/s00220-015-2492-8.
  25. Jian Ding, Allan Sly, and Nike Sun. Proof of the satisfiability conjecture for large k. Annals of Mathematics, 196(1):1-388, 2022. URL: https://doi.org/10.4007/annals.2022.196.1.1.
  26. Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm. arXiv preprint, 2014. URL: http://arxiv.org/abs/1411.4028.
  27. Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Leo Zhou. The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size. Quantum, 6:759, July 2022. URL: https://doi.org/10.22331/q-2022-07-07-759.
  28. Yaotian Fu and Philip W. Anderson. Application of statistical mechanics to NP-complete problems in combinatorial optimisation. Journal of Physics A: Mathematical and General, 19(9):1605-1620, June 1986. URL: https://doi.org/10.1088/0305-4470/19/9/033.
  29. David Gamarnik. The overlap gap property: A topological barrier to optimizing over random structures. Proceedings of the National Academy of Sciences, 118(41):e2108492118, 2021. Google Scholar
  30. David Gamarnik and Aukosh Jagannath. The overlap gap property and approximate message passing algorithms for p-spin models. The Annals of Probability, 49(1):180-205, 2021. Google Scholar
  31. David Gamarnik, Aukosh Jagannath, and Alexander S Wein. Low-degree hardness of random optimization problems. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 131-140. IEEE, 2020. Google Scholar
  32. David Gamarnik and Quan Li. Finding a large submatrix of a gaussian random matrix. The Annals of Statistics, 46(6A):2511-2561, 2018. Google Scholar
  33. David Gamarnik and Madhu Sudan. Limits of local algorithms over sparse random graphs. In Proceedings of the 5th conference on Innovations in Theoretical Computer Science, pages 369-376, 2014. Google Scholar
  34. Mrinalkanti Ghosh, Fernando Granha Jeronimo, Chris Jones, Aaron Potechin, and Goutham Rajendran. Sum-of-squares lower bounds for sherrington-kirkpatrick via planted affine planes. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 954-965. IEEE, 2020. Google Scholar
  35. Francesco Guerra. Broken replica symmetry bounds in the mean field spin glass model. Communications in Mathematical Physics, 233(1):1-12, 2003. Google Scholar
  36. Francesco Guerra and Fabio Lucio Toninelli. The high temperature region of the viana-bray diluted spin glass model. Journal of Statistical Physics, 115(1):531-555, 2004. Google Scholar
  37. Jun-Ting Hsieh, Sidhanth Mohanty, and Jeff Xu. Certifying solution geometry in random csps: counts, clusters and balance. arXiv preprint, 2021. URL: http://arxiv.org/abs/2106.12710.
  38. Brice Huang and Mark Sellke. Tight lipschitz hardness for optimizing mean field spin glasses. arXiv preprint, 2021. URL: http://arxiv.org/abs/2110.07847.
  39. Aukosh Jagannath and Subhabrata Sen. On the unbalanced cut problem and the generalized sherrington-kirkpatrick model. Annales de l’Institut Henri Poincaré D, 8(1):35-88, 2020. Google Scholar
  40. Subhash Khot. On the power of unique 2-prover 1-round games. In Proceedings of the thiry-fourth annual ACM Symposium on Theory of Computing, pages 767-775, 2002. Google Scholar
  41. Kunal Marwaha and Stuart Hadfield. Bounds on approximating max kxor with quantum and classical local algorithms. Quantum, 6:757, 2022. Google Scholar
  42. Marc Mézard, Giorgio Parisi, and Miguel Angel Virasoro. Spin glass theory and beyond: An Introduction to the Replica Method and Its Applications, volume 9. World Scientific Publishing Company, 1987. Google Scholar
  43. Andrea Montanari. Optimization of the sherrington-kirkpatrick hamiltonian. SIAM Journal on Computing, pages FOCS19-1-FOCS19-38, 2021. URL: https://doi.org/10.1137/20M132016X.
  44. Ryan O'Donnell. Analysis of boolean functions. Cambridge University Press, 2014. Google Scholar
  45. Dmitry Panchenko. Free energy in the generalized sherrington-kirkpatrick mean field model. Reviews in Mathematical Physics, 17(07):793-857, 2005. Google Scholar
  46. Dmitry Panchenko. The Sherrington-Kirkpatrick model. Springer Science & Business Media, 2013. Google Scholar
  47. Dmitry Panchenko. The Parisi formula for mixed p-spin models. The Annals of Probability, 42(3):946-958, 2014. URL: https://doi.org/10.1214/12-AOP800.
  48. Dmitry Panchenko. On the k-sat model with large number of clauses. Random Structures & Algorithms, 52(3):536-542, 2018. Google Scholar
  49. Dmitry Panchenko and Michel Talagrand. Bounds for diluted mean-fields spin glass models. Probability Theory and Related Fields, 130(3):319-336, 2004. Google Scholar
  50. Giorgio Parisi. A sequence of approximated solutions to the sk model for spin glasses. Journal of Physics A: Mathematical and General, 13(4):L115, 1980. Google Scholar
  51. Vangelis Th Paschos. Paradigms of Combinatorial Optimization: Problems and New Approaches, volume 2. John Wiley & Sons, 2013. Google Scholar
  52. Prasad Raghavendra. Optimal algorithms and inapproximability results for every csp? In Proceedings of the fortieth annual ACM Symposium on Theory of Computing, pages 245-254, 2008. Google Scholar
  53. Mustazee Rahman and Balint Virag. Local algorithms for independent sets are half-optimal. The Annals of Probability, 45(3):1543-1577, 2017. Google Scholar
  54. Mark Sellke. Optimizing mean field spin glasses with external field. arXiv preprint, 2021. URL: http://arxiv.org/abs/2105.03506.
  55. Subhabrata Sen. Optimization on sparse random hypergraphs and spin glasses. Random Structures & Algorithms, 53(3):504-536, 2018. Google Scholar
  56. David Sherrington and Scott Kirkpatrick. Solvable model of a spin-glass. Physical Review Letters, 35(26):1792, 1975. Google Scholar
  57. Eliran Subag. Following the ground-states of full-rsb spherical spin glasses, 2018. URL: http://arxiv.org/abs/1812.04588.
  58. Michel Talagrand. The parisi formula. Annals of Mathematics, pages 221-263, 2006. 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