Fast Algorithms at Low Temperatures via Markov Chains

Authors Zongchen Chen, Andreas Galanis, Leslie Ann Goldberg, Will Perkins, James Stewart, Eric Vigoda



PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2019.41.pdf
  • Filesize: 0.5 MB
  • 14 pages

Document Identifiers

Author Details

Zongchen Chen
  • School of Computer Science, Georgia Institute of Technology, Atlanta, USA
Andreas Galanis
  • Department of Computer Science, University of Oxford, Oxford, UK
Leslie Ann Goldberg
  • Department of Computer Science, University of Oxford, Oxford, UK
Will Perkins
  • Department of Mathematics, Statistics, and Computer Science, University of Illinois at Chicago, Chicago, USA
James Stewart
  • Department of Computer Science, University of Oxford, Oxford, UK
Eric Vigoda
  • School of Computer Science, Georgia Institute of Technology, Atlanta, USA

Cite AsGet BibTex

Zongchen Chen, Andreas Galanis, Leslie Ann Goldberg, Will Perkins, James Stewart, and Eric Vigoda. Fast Algorithms at Low Temperatures via Markov Chains. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 41:1-41:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.41

Abstract

For spin systems, such as the hard-core model on independent sets weighted by fugacity lambda>0, efficient algorithms for the associated approximate counting/sampling problems typically apply in the high-temperature region, corresponding to low fugacity. Recent work of Jenssen, Keevash and Perkins (2019) yields an FPTAS for approximating the partition function (and an efficient sampling algorithm) on bounded-degree (bipartite) expander graphs for the hard-core model at sufficiently high fugacity, and also the ferromagnetic Potts model at sufficiently low temperatures. Their method is based on using the cluster expansion to obtain a complex zero-free region for the partition function of a polymer model, and then approximating this partition function using the polynomial interpolation method of Barvinok. We present a simple discrete-time Markov chain for abstract polymer models, and present an elementary proof of rapid mixing of this new chain under sufficient decay of the polymer weights. Applying these general polymer results to the hard-core and ferromagnetic Potts models on bounded-degree (bipartite) expander graphs yields fast algorithms with running time O(n log n) for the Potts model and O(n^2 log n) for the hard-core model, in contrast to typical running times of n^{O(log Delta)} for algorithms based on Barvinok’s polynomial interpolation method on graphs of maximum degree Delta. In addition, our approach via our polymer model Markov chain is conceptually simpler as it circumvents the zero-free analysis and the generalization to complex parameters. Finally, we combine our results for the hard-core and ferromagnetic Potts models with standard Markov chain comparison tools to obtain polynomial mixing time for the usual spin system Glauber dynamics restricted to even and odd or "red" dominant portions of the respective state spaces.

Subject Classification

ACM Subject Classification
  • Theory of computation → Random walks and Markov chains
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Markov chains
  • approximate counting
  • Potts model
  • hard-core model
  • expander graphs

Metrics

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

References

  1. A. Barvinok. Combinatorics and Complexity of Partition Functions. Algorithms and Combinatorics. Springer International Publishing, 2017. Google Scholar
  2. I. Bezáková, D. Štefankovič, V. V. Vazirani, and E. Vigoda. Accelerating simulated annealing for the permanent and combinatorial counting problems. SIAM Journal on Computing, 37(5):1429-1454, 2008. Google Scholar
  3. C. Borgs. Absence of zeros for the chromatic polynomial on bounded degree graphs. Combinatorics, Probability and Computing, 15(1-2):63-74, 2006. Google Scholar
  4. C. Borgs, J. T. Chayes, A. Frieze, J. H. Kim, P. Tetali, E. Vigoda, and V. H. Vu. Torpid mixing of some Monte Carlo Markov chain algorithms in statistical physics. In Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 218-229, 1999. Google Scholar
  5. C. Borgs, J. T. Chayes, J. Kahn, and L. Lovász. Left and right convergence of graphs with bounded degree. Random Structures & Algorithms, 42(1):1-28, 2013. Google Scholar
  6. C. Borgs and J. Z. Imbrie. A unified approach to phase diagrams in field theory and statistical mechanics. Communications in mathematical physics, 123(2):305-328, 1989. Google Scholar
  7. R. L. Dobrushin. Estimates of semi-invariants for the Ising model at low temperatures. Translations of the American Mathematical Society-Series 2, 177:59-82, 1996. Google Scholar
  8. M. E. Dyer and C. S. Greenhill. On Markov Chains for Independent Sets. J. Algorithms, 35(1):17-49, 2000. URL: https://doi.org/10.1006/jagm.1999.1071.
  9. Martin Dyer and Catherine Greenhill. Random walks on combinatorial objects. London Mathematical Society Lecture Note Series, pages 101-136, 1999. Google Scholar
  10. C. Efthymiou, T. P. Hayes, D. Štefankovič, E. Vigoda, and Y. Yin. Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model. In Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 704-713, 2016. Google Scholar
  11. R. Fernández, P. A. Ferrari, and N. L. Garcia. Loss network representation of Peierls contours. Annals of Probability, 29(2):902-937, 2001. Google Scholar
  12. D. Galvin and P. Tetali. Slow mixing of Glauber dynamics for the hard-core model on regular bipartite graphs. Random Structures & Algorithms, 28(4):427-443, 2006. Google Scholar
  13. C. Gruber and H. Kunz. General properties of polymer systems. Communications in Mathematical Physics, 22(2):133-161, 1971. Google Scholar
  14. T. Helmuth, W. Perkins, and G. Regts. Algorithmic Pirogov-Sinai theory. arXiv preprint, http://arxiv.org/abs/1806.11548, 2018.
  15. M. Huber. Approximation algorithms for the normalizing constant of Gibbs distributions. The Annals of Applied Probability, 25(2):974-985, 2015. Google Scholar
  16. M. Jenssen, P. Keevash, and W. Perkins. Algorithms for #BIS-hard problems on expander graphs. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2235-2247. SIAM, 2019. Google Scholar
  17. M. Jenssen, P. Keevash, and W. Perkins. Algorithms for #BIS-hard problems on expander graphs. arXiv preprint, 2019. URL: http://arxiv.org/abs/1807.04804v2.
  18. R. Kotecký and D. Preiss. Cluster expansion for abstract polymer models. Communications in Mathematical Physics, 103(3):491-498, 1986. URL: http://projecteuclid.org/euclid.cmp/1104114796.
  19. L. Laanait, A. Messager, S. Miracle-Solé, J. Ruiz, and S. Shlosman. Interfaces in the Potts model I: Pirogov-Sinai theory of the Fortuin-Kasteleyn representation. Communications in Mathematical Physics, 140(1):81-91, 1991. Google Scholar
  20. C. Liao, J. Lin, P. Lu, and Z. Mao. Counting independent sets and colorings on random regular bipartite graphs. arXiv preprint, 2019. URL: http://arxiv.org/abs/1903.07531.
  21. J. Liu and P. Lu. FPTAS for #BIS with degree bounds on one side. In Proceedings of the 47th Annual ACM on Symposium on Theory of Computing (STOC), pages 549-556, 2015. Google Scholar
  22. E. Mossel, D. Weitz, and N. Wormald. On the hardness of sampling independent sets beyond the tree threshold. Probability Theory and Related Fields, 143(3-4):401-439, 2009. Google Scholar
  23. V. Patel and G. Regts. Deterministic polynomial-time approximation algorithms for functions and graph polynomials. SIAM Journal on Computing, 46(6):1893-1919, 2017. Google Scholar
  24. S. A. Pirogov and Ya. G. Sinai. Phase diagrams of classical lattice systems. Teoret. Mat. Fiz., 25(3):358-369, 1975. Google Scholar
  25. D. Štefankovič, S. Vempala, and E. Vigoda. Adaptive simulated annealing: A near-optimal connection between sampling and counting. Journal of the ACM, 56(3):18, 2009. Google Scholar
  26. D. Weitz. Counting independent sets up to the tree threshold. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC), pages 140-149, 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