Document Open Access Logo

On Sampling Symmetric Gibbs Distributions on Sparse Random Graphs and Hypergraphs

Author Charilaos Efthymiou

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2022.57.pdf
  • Filesize: 0.7 MB
  • 16 pages

Document Identifiers

Author Details

Charilaos Efthymiou
  • Computer Science, University of Warwick, Coventry, UK

Funding

  • Efthymiou, Charilaos: EPSRC New Investigator Award (grant no. EP/V050842/1) and Centre of Discrete Mathematics and Applications (DIMAP), The University of Warwick.

Acknowledgements

The author of this work would like to thank Amin Coja-Oghlan for the fruitful discussions.

Cite AsGet BibTex

Charilaos Efthymiou. On Sampling Symmetric Gibbs Distributions on Sparse Random Graphs and Hypergraphs. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 57:1-57:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ICALP.2022.57

Abstract

In this paper, we present a novel, polynomial time, algorithm for approximate sampling from symmetric Gibbs distributions on the sparse random graph and hypergraph. The examples of symmetric distributions we consider here include some important distributions on spin-systems and spin-glasses. These are: the q-state antiferromagnetic Potts model for q ≥ 2, including the (hyper)graph Ising model and random colourings. The uniform distribution over the Not-All-Equal solutions of a random k-SAT formula. Finally, we consider sampling from the spin-glass distribution called the k-spin model, i.e., this is the "diluted" version of the well-known Sherrington-Kirkpatrick model. Spin-glasses give rise to very intricate distributions which are also studied in mathematics, in neural computation, computational biology and many other areas. To our knowledge, this is the first rigorously analysed efficient sampling algorithm for spin-glasses which operates in a non trivial range of the parameters of the distribution. We present, what we believe to be, an elegant sampling algorithm. Our algorithm is unique in its approach and does not belong to any of the well-known families of sampling algorithms. We derive it by investigating the power and the limits of the approach that was introduced in [Efthymiou: SODA 2012] and combine it, in a novel way, with powerful notions from the Cavity method. Specifically, for a symmetric Gibbs distribution μ on the random (hyper)graph whose parameters are within an appropriate range, our sampling algorithm has the following properties: with probability 1-o(1) over the instances of the input (hyper)graph, it generates a configuration which is distributed within total variation distance n^{-Ω(1)} from μ. The time complexity is O((nlog n)²), where n is the size of the input (hyper)graph. We make a notable progress regarding impressive predictions of physicists relating phase-transitions of Gibbs distributions with the efficiency of the corresponding sampling algorithms. For most (if not all) the cases we consider here, our algorithm outperforms by far any other sampling algorithms in terms of the permitted range of the parameters of the Gibbs distributions. The use of notions and ideas from the Cavity method provides a new insight to the sampling problem. Our results imply that there is a lot of potential for further exploiting the Cavity method for algorithmic design.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
  • Theory of computation → Randomness, geometry and discrete structures
  • Mathematics of computing → Discrete mathematics
Keywords
  • spin-system
  • spin-glass
  • sparse random (hyper)graph
  • approximate sampling
  • efficient algorithm

Metrics

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

Related Versions

References

  1. Dimitris Achlioptas and Amin Coja-Oghlan. Algorithmic barriers from phase transitions. In 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 25-28, 2008, Philadelphia, PA, USA, pages 793-802. IEEE Computer Society, 2008. URL: https://doi.org/10.1109/FOCS.2008.11.
  2. Dimitris Achlioptas and Cristopher Moore. Random k-sat: Two moments suffice to cross a sharp threshold. SIAM J. Comput., 36(3):740-762, 2006. URL: https://doi.org/10.1137/S0097539703434231.
  3. Nima Anari, Kuikui Liu, and Shayan Oveis Gharan. Spectral independence in high-dimensional expanders and applications to the hardcore model. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 1319-1330. IEEE, 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00125.
  4. Antonio Blanca, Andreas Galanis, Leslie Ann Goldberg, Daniel Stefankovic, Eric Vigoda, and Kuan Yang. Sampling in uniqueness from the potts and random-cluster models on random regular graphs. SIAM J. Discret. Math., 34(1):742-793, 2020. URL: https://doi.org/10.1137/18M1219722.
  5. Alfredo Braunstein, Marc Mézard, and Riccardo Zecchina. Survey propagation: An algorithm for satisfiability. Random Struct. Algorithms, 27(2):201-226, 2005. URL: https://doi.org/10.1002/rsa.20057.
  6. Sitan Chen, Michelle Delcourt, Ankur Moitra, Guillem Perarnau, and Luke Postle. Improved bounds for randomly sampling colorings via linear programming. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 2216-2234. SIAM, 2019. URL: https://doi.org/10.1137/1.9781611975482.134.
  7. Amin Coja-Oghlan, Charilaos Efthymiou, and Nor Jaafari. Local convergence of random graph colorings. Combinatorica, 38(2):341-380, 2018. URL: https://doi.org/10.1007/s00493-016-3394-x.
  8. Amin Coja-Oghlan, Charilaos Efthymiou, Nor Jaafari, Mihyun Kang, and Tobias Kapetanopoulos. Charting the replica symmetric phase. Communications in Mathematical Physics, 359(2):603-698, 2018. URL: https://doi.org/10.1007/s00220-018-3096-x.
  9. Amin Coja-Oghlan and Alan M. Frieze. Analyzing walksat on random formulas. SIAM J. Comput., 43(4):1456-1485, 2014. URL: https://doi.org/10.1137/12090191X.
  10. Amin Coja-Oghlan, Tobias Kapetanopoulos, and Noëla Müller. The replica symmetric phase of random constraint satisfaction problems. Comb. Probab. Comput., 29(3):346-422, 2020. URL: https://doi.org/10.1017/S0963548319000440.
  11. Amin Coja-Oghlan, Florent Krzakala, Will Perkins, and Lenka Zdeborová. Information-theoretic thresholds from the cavity method. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 146-157. ACM, 2017. URL: https://doi.org/10.1145/3055399.3055420.
  12. Jian Ding, Allan Sly, and Nike Sun. Proof of the satisfiability conjecture for large k. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 59-68. ACM, 2015. URL: https://doi.org/10.1145/2746539.2746619.
  13. Martin E. Dyer and Alan M. Frieze. Randomly coloring graphs with lower bounds on girth and maximum degree. Random Struct. Algorithms, 23(2):167-179, 2003. URL: https://doi.org/10.1002/rsa.10087.
  14. Martin E. Dyer, Alan M. Frieze, Thomas P. Hayes, and Eric Vigoda. Randomly coloring constant degree graphs. Random Struct. Algorithms, 43(2):181-200, 2013. URL: https://doi.org/10.1002/rsa.20451.
  15. Charilaos Efthymiou. A simple algorithm for random colouring G(n, d/n) using (2 + ε)d colours. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012, pages 272-280. SIAM, 2012. URL: https://doi.org/10.1137/1.9781611973099.25.
  16. Charilaos Efthymiou. Reconstruction/non-reconstruction thresholds for colourings of general galton-watson trees. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2015, August 24-26, 2015, Princeton, NJ, USA, volume 40 of LIPIcs, pages 756-774. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.756.
  17. Charilaos Efthymiou. A simple algorithm for sampling colorings of G(n, d/n) up to the gibbs uniqueness threshold. SIAM J. Comput., 45(6):2087-2116, 2016. URL: https://doi.org/10.1137/140977643.
  18. Charilaos Efthymiou, Thomas P. Hayes, Daniel Stefankovic, and Eric Vigoda. Sampling random colorings of sparse random graphs. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 1759-1771. SIAM, 2018. URL: https://doi.org/10.1137/1.9781611975031.115.
  19. Uriel Feige. Relations between average case complexity and approximation complexity. In Proceedings on 34th Annual ACM Symposium on Theory of Computing, May 19-21, 2002, Montréal, Québec, Canada, pages 534-543. ACM, 2002. URL: https://doi.org/10.1145/509907.509985.
  20. Vitaly Feldman, Will Perkins, and Santosh S. Vempala. On the complexity of random satisfiability problems with planted solutions. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 77-86. ACM, 2015. URL: https://doi.org/10.1145/2746539.2746577.
  21. Alan Frieze and Eric Vigoda. A survey on the use of markov chains to randomly sample colorings. In Combinatorics, Complexity, and Chance, pages 53-71. Oxford University Press, January 2007. URL: https://doi.org/10.1093/acprof:oso/9780198571278.003.0004.
  22. Alan M. Frieze and Michael Anastos. Randomly coloring simple hypergraphs with fewer colors. Inf. Process. Lett., 126:39-42, 2017. URL: https://doi.org/10.1016/j.ipl.2017.06.005.
  23. Andreas Galanis, Daniel Stefankovic, and Eric Vigoda. Inapproximability for antiferromagnetic spin systems in the tree nonuniqueness region. J. ACM, 62(6):50:1-50:60, 2015. URL: https://doi.org/10.1145/2785964.
  24. Andrei Giurgiu, Nicolas Macris, and Rüdiger Urbanke. Spatial coupling as a proof technique and three applications. IEEE Transactions on Information Theory, 62(10):5281-5295, 2016. URL: https://doi.org/10.1109/TIT.2016.2539144.
  25. Leslie Ann Goldberg, Russell A. Martin, and Mike Paterson. Strong spatial mixing with fewer colors for lattice graphs. SIAM J. Comput., 35(2):486-517, 2005. URL: https://doi.org/10.1137/S0097539704445470.
  26. Oded Goldreich. Candidate One-Way Functions Based on Expander Graphs, pages 76-87. Springer Berlin Heidelberg, Berlin, Heidelberg, 2011. URL: https://doi.org/10.1007/978-3-642-22670-0_10.
  27. Thomas P. Hayes, Juan Carlos Vera, and Eric Vigoda. Randomly coloring planar graphs with fewer colors than the maximum degree. Random Struct. Algorithms, 47(4):731-759, 2015. URL: https://doi.org/10.1002/rsa.20560.
  28. Mark Jerrum. Counting, Sampling and Integrating: Algorithm and Complexity. Lectures in Mathematics ETH. Birkhäuser Basel, 1st edition, 2003. Google Scholar
  29. Florent Krzakala, Andrea Montanari, Federico Ricci-Tersenghi, Guilhem Semerjian, and Lenka Zdeborová. Gibbs states and the set of solutions of random constraint satisfaction problems. Proceedings of the National Academy of Sciences, 104(25):10318-10323, 2007. URL: https://doi.org/10.1073/pnas.0703685104.
  30. Florent Krzakala and Lenka Zdeborová. Hiding quiet solutions in random constraint satisfaction problems. Phys. Rev. Lett., 102:238701, June 2009. URL: https://doi.org/10.1103/PhysRevLett.102.238701.
  31. M Mezard, G Parisi, and M Virasoro. Spin Glass Theory and Beyond. WORLD SCIENTIFIC, 1986. URL: https://doi.org/10.1142/0271.
  32. M. Mézard, G. Parisi, and R. Zecchina. Analytic and algorithmic solution of random satisfiability problems. Science, 297(5582):812-815, 2002. URL: https://doi.org/10.1126/science.1073287.
  33. Marc Mézard and Andrea Montanari. Information, Physics, and Computation. Oxford Graduate Texts. Oxford University Press, Oxford, 2009. Google Scholar
  34. Michael Molloy. The freezing threshold for k-colourings of a random graph. J. ACM, 65(2):7:1-7:62, 2018. URL: https://doi.org/10.1145/3034781.
  35. Elchanan Mossel and Allan Sly. Exact thresholds for Ising-Gibbs samplers on general graphs. The Annals of Probability, 41(1):294-328, 2013. URL: https://doi.org/10.1214/11-AOP737.
  36. Sheldon M Ross. Stochastic Processes. John Wiley & Sons, Nashville, TN, 2 edition, January 1995. Google Scholar
  37. Daniel L Stein and Charles M Newman. Spin Glasses and Complexity. Princeton University Press, January 2013. Google Scholar
  38. Michel Talagrand. The Parisi formula. Ann. Math. (2), 163(1):221-263, 2006. URL: https://doi.org/10.4007/annals.2006.163.221.
  39. Eric Vigoda. Improved bounds for sampling colorings. In 40th Annual Symposium on Foundations of Computer Science, FOCS '99, 17-18 October, 1999, New York, NY, USA, pages 51-59. IEEE Computer Society, 1999. URL: https://doi.org/10.1109/SFFCS.1999.814577.
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