More Web Proxy on the site http://driver.im/

research-article

Open access

Efficient sampling and counting algorithms for the Potts model on ℤᵈ at all temperatures

Authors:

Christian Borgs,

Jennifer Chayes,

Prasad TetaliAuthors Info & Claims

STOC 2020: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing

Pages 738 - 751

https://doi.org/10.1145/3357713.3384271

Published: 22 June 2020 Publication History

Abstract

For d ≥ 2 and all q≥ q ₀(d) we give an efficient algorithm to approximately sample from the q-state ferromagnetic Potts and random cluster models on the torus (ℤ / n ℤ )^d for any inverse temperature β≥ 0. This stands in contrast to Markov chain mixing time results: the Glauber dynamics mix slowly at and below the critical temperature, and the Swendsen–Wang dynamics mix slowly at the critical temperature. We also provide an efficient algorithm (an FPRAS) for approximating the partition functions of these models.

Our algorithms are based on representing the random cluster model as a contour model using Pirogov–Sinai theory, and then computing an accurate approximation of the logarithm of the partition function by inductively truncating the resulting cluster expansion. One important innovation of our approach is an algorithmic treatment of unstable ground states; this is essential for our algorithms to apply to all inverse temperatures β. By treating unstable ground states our work gives a general template for converting probabilistic applications of Pirogov–Sinai theory to efficient algorithms.

References

[1]

Dimitris Achlioptas and Amin Coja-Oghlan. 2008. Algorithmic barriers from phase transitions. In 2008 49th Annual IEEE Symposium on Foundations of Computer Science. IEEE, 793-802.

Digital Library

[2]

Kenneth S Alexander. 2004. Mixing properties and exponential decay for lattice systems in finite volumes. The Annals of Probability 32, 1A ( 2004 ), 441-487.

[3]

Alexander Barvinok. 2017. Combinatorics and Complexity of Partition Functions. Algorithms and Combinatorics 30 ( 2017 ).

[4]

Alexander Barvinok and Guus Regts. 2019. Weighted counting of solutions to sparse systems of equations. Combinatorics, Probability and Computing 28, 5 ( 2019 ), 696-719.

[5]

Antonio Blanca and Alistair Sinclair. 2017. Random-cluster dynamics in Z2. Probability Theory and Related Fields 168, 3-4 ( 2017 ), 821-847.

[6]

Magnus Bordewich, Catherine Greenhill, and Viresh Patel. 2016. Mixing of the Glauber dynamics for the ferromagnetic Potts model. Random Structures & Algorithms 48, 1 ( 2016 ), 21-52.

[7]

C Borgs, J Chayes, T Helmuth, W Perkins, and P Tetali. 2019. Eficient sampling and counting algorithms for the Potts model on Zd at all temperatures. arXiv preprint arXiv: 1909. 09298 ( 2019 ).

[8]

Christian Borgs, Jennifer T Chayes, and Prasad Tetali. 2012. Tight bounds for mixing of the Swendsen-Wang algorithm at the Potts transition point. Probability Theory and Related Fields 152, 3-4 ( 2012 ), 509-557.

[9]

Christian Borgs and John Z Imbrie. 1989. A unified approach to phase diagrams in ifeld theory and statistical mechanics. Communications in mathematical physics 123, 2 ( 1989 ), 305-328.

[10]

Christian Borgs, Roman Kotecký, and Salvador Miracle-Solé. 1991. Finite-size scaling for Potts models. Journal of Statistical Physics 62, 3-4 ( 1991 ), 529-551.

[11]

Sarah Cannon and Will Perkins. 2019. Counting independent sets in unbalanced bipartite graphs. arXiv preprint arXiv: 1906. 01666 ( 2019 ).

[12]

Katrin Casel, Philipp Fischbeck, Tobias Friedrich, Andreas Göbel, and JA Lagodzinski. 2019. Zeros and approximations of Holant polynomials on the complex plane. arXiv preprint arXiv: 1905. 03194 ( 2019 ).

[13]

Zongchen Chen, Andreas Galanis, Leslie Ann Goldberg, Will Perkins, James Stewart, and Eric Vigoda. 2019. Fast algorithms at low temperatures via Markov chains. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019 ). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.

[14]

Aurelien Decelle, Florent Krzakala, Cristopher Moore, and Lenka Zdeborová. 2011. Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications. Physical Review E 84, 6 ( 2011 ), 066106.

[15]

Hugo Duminil-Copin. 2017. Lectures on the Ising and Potts models on the hypercubic lattice. arXiv preprint arXiv:1707.00520 ( 2017 ).

[16]

Hugo Duminil-Copin, Aran Raoufi, and Vincent Tassion. 2019. Sharp phase transition for the random-cluster and Potts models via decision trees. Annals of Mathematics 189, 1 ( 2019 ), 75-99.

[17]

Sacha Friedli and Yvan Velenik. 2017. Statistical mechanics of lattice systems: a concrete mathematical introduction. Cambridge University Press.

[18]

Andreas Galanis, Qi Ge, Daniel Štefankovič, Eric Vigoda, and Linji Yang. 2011. Improved inapproximability results for counting independent sets in the hardcore model. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Springer, 567-578.

[19]

Andreas Galanis, Daniel Stefankovic, Eric Vigoda, and Linji Yang. 2016. Ferromagnetic Potts model: Refined #-BIS-hardness and related results. SIAM J. Comput. 45, 6 ( 2016 ), 2004-2065.

[20]

David Gamarnik and Madhu Sudan. 2017. Performance of sequential local algorithms for the random NAE-K-SAT problem. SIAM J. Comput. 46, 2 ( 2017 ), 590-619.

[21]

Reza Gheissari and Eyal Lubetzky. 2018. Mixing Times of Critical TwoDimensional Potts Models. Communications on Pure and Applied Mathematics 71, 5 ( 2018 ), 994-1046.

[22]

Reza Gheissari and Eyal Lubetzky. 2020. Quasi-polynomial mixing of critical two-dimensional random cluster models. Random Structures & Algorithms 56, 2 ( 2020 ), 517-556.

[23]

Leslie Ann Goldberg and Mark Jerrum. 2012. Approximating the partition function of the ferromagnetic Potts model. J. ACM 59, 5 ( 2012 ), 25.

Digital Library

[24]

C Gruber and H Kunz. 1971. General properties of polymer systems. Communications in Mathematical Physics 22, 2 ( 1971 ), 133-161.

[25]

Heng Guo and Mark Jerrum. 2018. Random cluster dynamics for the Ising model is rapidly mixing. Ann. Appl. Probab. 28, 2 ( 04 2018 ), 1292-1313.

[26]

Tyler Helmuth, Will Perkins, and Guus Regts. to appear. An extended abstract appeared at STOC 2019. Algorithmic Pirogov-Sinai theory. Probability Theory and Related Fields (to appear. An extended abstract appeared at STOC 2019.).

[27]

Matthew Jenssen, Peter Keevash, and Will Perkins. 2019. Full version at http://arxiv.org/abs/ 1807.04804v2. Algorithms for #BIS-hard problems on expander graphs. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019 ). SIAM, 2235-2247.

[28]

Mark Jerrum and Alistair Sinclair. 1993. Polynomial-time approximation algorithms for the Ising model. SIAM Journal on computing 22, 5 ( 1993 ), 1087-1116.

[29]

Roman Kotecký and David Preiss. 1986. Cluster expansion for abstract polymer models. Communications in Mathematical Physics 103, 3 ( 1986 ), 491-498.

[30]

Roman Kotecky` and SB Shlosman. 1982. First-order phase transitions in large entropy lattice models. Communications in Mathematical Physics 83, 4 ( 1982 ), 493-515.

[31]

Florent Krzakała, Andrea Montanari, Federico Ricci-Tersenghi, Guilhem Semerjian, and Lenka Zdeborová. 2007. Gibbs states and the set of solutions of random constraint satisfaction problems. Proceedings of the National Academy of Sciences 104, 25 ( 2007 ), 10318-10323.

[32]

Lahoussine Laanait, Alain Messager, Salvador Miracle-Solé, Jean Ruiz, and Senya Shlosman. 1991. Interfaces in the Potts model I: Pirogov-Sinai theory of the Fortuin-Kasteleyn representation. Communications in Mathematical Physics 140, 1 ( 1991 ), 81-91.

[33]

Tsung-Dao Lee and Chen-Ning Yang. 1952. Statistical theory of equations of state and phase transitions. II. Lattice gas and Ising model. Physical Review 87, 3 ( 1952 ), 410.

[34]

Chao Liao, Jiabao Lin, Pinyan Lu, and Zhenyu Mao. 2019. Counting independent sets and colorings on random regular bipartite graphs. arXiv preprint arXiv: 1903. 07531 ( 2019 ).

[35]

Fabio Martinelli, Enzo Olivieri, and Roberto H Schonmann. 1994. For 2-d lattice spin systems weak mixing implies strong mixing. Communications in Mathematical Physics 165, 1 ( 1994 ), 33-47.

[36]

Viresh Patel and Guus Regts. 2017. Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials. SIAM J. Comput. 46, 6 ( 2017 ), 1893-1919.

[37]

Ron Peled and Yinon Spinka. 2018. Rigidity of proper colorings of Zd. arXiv preprint arXiv: 1808. 03597 ( 2018 ).

[38]

Sergey Anatol'evich Pirogov and Ya G Sinai. 1975. Phase diagrams of classical lattice systems. Theoretical and Mathematical Physics 25, 3 ( 1975 ), 1185-1192.

[39]

Allan Sly. 2010. Computational transition at the uniqueness threshold. In Proceedings of the Fifty-first Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010 ). IEEE, 287-296.

Digital Library

[40]

Allan Sly and Nike Sun. 2014. Counting in two-spin models on d-regular graphs. The Annals of Probability 42, 6 ( 2014 ), 2383-2416.

[41]

Daniel Štefankovič, Santosh Vempala, and Eric Vigoda. 2009. Adaptive simulated annealing: A near-optimal connection between sampling and counting. Journal of the ACM (JACM) 56, 3 ( 2009 ), 18.

Digital Library

[42]

Mario Ullrich. 2013. Comparison of Swendsen-Wang and heat-bath dynamics. Random Structures & Algorithms 42, 4 ( 2013 ), 520-535.

[43]

Dror Weitz. 2006. Counting independent sets up to the tree threshold. In Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing (STOC 2006 ). ACM, 140-149.

Digital Library

Cited By

Blanca ACannon SPerkins W(2024)Fast and Perfect Sampling of Subgraphs and Polymer SystemsACM Transactions on Algorithms10.1145/363229420:1(1-30)Online publication date: 22-Jan-2024
https://dl.acm.org/doi/10.1145/3632294
Galanis AGoldberg LSmolarova P(2024)Sampling from the random cluster model on random regular graphs at all temperatures via Glauber dynamicsCombinatorics, Probability and Computing10.1017/S0963548324000403(1-33)Online publication date: 9-Dec-2024
https://doi.org/10.1017/S0963548324000403
Carlson CDavies EFraiman NKolla APotukuchi AYap C(2024)Algorithms for the ferromagnetic Potts model on expandersCombinatorics, Probability and Computing10.1017/S0963548324000087(1-31)Online publication date: 5-Apr-2024
https://doi.org/10.1017/S0963548324000087
Show More Cited By

Recommendations

Sampling in Uniqueness from the Potts and Random-Cluster Models on Random Regular Graphs

We consider the problem of sampling from the Potts model on random regular graphs. It is conjectured that sampling is possible when the temperature of the model is in the so-called uniqueness regime of the regular tree, but positive algorithmic results ...
Approximating the partition function of the ferromagnetic Potts model

We provide evidence that it is computationally difficult to approximate the partition function of the ferromagnetic q-state Potts model when q > 2. Specifically, we show that the partition function is hard for the complexity class #RHPi under ...
Modified q-State Potts Model with Binarized Synaptic Coefficients
ICANN '08: Proceedings of the 18th international conference on Artificial Neural Networks, Part II

Practical applications of q -state Potts models are complicated, as they require very large RAM (32 N ² q ²bits, where N is the number of neurons and q is the number of the states of a neuron). In this work we examine a modified Potts model with ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC 2020: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing

June 2020

1429 pages

ISBN:9781450369794

DOI:10.1145/3357713

General Chairs:
Konstantin Makarychev
Northwestern University, USA
,
Yury Makarychev
Toyota Technological Institute at Chicago, USA
,
Madhur Tulsiani
Toyota Technological Institute at Chicago, USA
,
Gautam Kamath
University of Waterloo, Canada
,
Program Chair:
Julia Chuzhoy
Toyota Technological Institute at Chicago, USA

Copyright © 2020 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 June 2020

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

STOC '20

Sponsor:

SIGACT

STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing

June 22 - 26, 2020

IL, Chicago, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

20
Total Citations
View Citations
533
Total Downloads

Downloads (Last 12 months)205
Downloads (Last 6 weeks)40

Reflects downloads up to 14 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Blanca ACannon SPerkins W(2024)Fast and Perfect Sampling of Subgraphs and Polymer SystemsACM Transactions on Algorithms10.1145/363229420:1(1-30)Online publication date: 22-Jan-2024
https://dl.acm.org/doi/10.1145/3632294
Galanis AGoldberg LSmolarova P(2024)Sampling from the random cluster model on random regular graphs at all temperatures via Glauber dynamicsCombinatorics, Probability and Computing10.1017/S0963548324000403(1-33)Online publication date: 9-Dec-2024
https://doi.org/10.1017/S0963548324000403
Carlson CDavies EFraiman NKolla APotukuchi AYap C(2024)Algorithms for the ferromagnetic Potts model on expandersCombinatorics, Probability and Computing10.1017/S0963548324000087(1-31)Online publication date: 5-Apr-2024
https://doi.org/10.1017/S0963548324000087
Jenssen M(2024)The Cluster Expansion in CombinatoricsSurveys in Combinatorics 202410.1017/9781009490559.004(55-88)Online publication date: 23-May-2024
https://doi.org/10.1017/9781009490559.004
Blanca AGheissari R(2024)On the tractability of sampling from the Potts model at low temperatures via random-cluster dynamicsProbability Theory and Related Fields10.1007/s00440-024-01289-xOnline publication date: 8-Jun-2024
https://doi.org/10.1007/s00440-024-01289-x
Helmuth TMann R(2023)Efficient Algorithms for Approximating Quantum Partition Functions at Low TemperatureQuantum10.22331/q-2023-10-25-11557(1155)Online publication date: 25-Oct-2023
https://doi.org/10.22331/q-2023-10-25-1155
Blanca AGheissari R(2023)Sampling from Potts on random graphs of unbounded degree via random-cluster dynamicsThe Annals of Applied Probability10.1214/23-AAP193933:6BOnline publication date: 1-Dec-2023
https://doi.org/10.1214/23-AAP1939
Helmuth TJenssen MPerkins W(2023)Finite-size scaling, phase coexistence, and algorithms for the random cluster model on random graphsAnnales de l'Institut Henri Poincaré, Probabilités et Statistiques10.1214/22-AIHP126359:2Online publication date: 1-May-2023
https://doi.org/10.1214/22-AIHP1263
Gheissari RSinclair A(2023)Low-temperature Ising dynamics with random initializationsThe Annals of Applied Probability10.1214/22-AAP191133:5Online publication date: 1-Oct-2023
https://doi.org/10.1214/22-AAP1911
Blanca AGheissari R(2023)Sampling from the Potts model at low temperatures via Swendsen–Wang dynamics2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00122(2006-2020)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00122
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents