{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T16:36:21Z","timestamp":1787502981534,"version":"build-2736575974"},"publisher-location":"New York, NY, USA","reference-count":43,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T00:00:00Z","timestamp":1592784000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/P003656\/1"],"award-info":[{"award-number":["EP\/P003656\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100007515","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-1847451, DMS-1811935"],"award-info":[{"award-number":["DMS-1847451, DMS-1811935"]}],"id":[{"id":"10.13039\/100007515","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,6,22]]},"DOI":"10.1145\/3357713.3384271","type":"proceedings-article","created":{"date-parts":[[2020,6,6]],"date-time":"2020-06-06T21:45:25Z","timestamp":1591479925000},"page":"738-751","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":20,"title":["Efficient sampling and counting algorithms for the Potts model on \u2124\u1d48 at all temperatures"],"prefix":"10.1145","author":[{"given":"Christian","family":"Borgs","sequence":"first","affiliation":[{"name":"University of California at Berkeley, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jennifer","family":"Chayes","sequence":"additional","affiliation":[{"name":"University of California at Berkeley, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tyler","family":"Helmuth","sequence":"additional","affiliation":[{"name":"University of Bristol, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7937-7016","authenticated-orcid":false,"given":"Will","family":"Perkins","sequence":"additional","affiliation":[{"name":"University of Illinois at Chicago, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Prasad","family":"Tetali","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,6,22]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.11"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1078415842"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Alexander Barvinok. 2017. Combinatorics and Complexity of Partition Functions. Algorithms and Combinatorics 30 ( 2017 ).  Alexander Barvinok. 2017. Combinatorics and Complexity of Partition Functions. Algorithms and Combinatorics 30 ( 2017 ).","DOI":"10.1007\/978-3-319-51829-9"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Alexander Barvinok and Guus Regts. 2019. Weighted counting of solutions to sparse systems of equations. Combinatorics Probability and Computing 28 5 ( 2019 ) 696-719.  Alexander Barvinok and Guus Regts. 2019. Weighted counting of solutions to sparse systems of equations. Combinatorics Probability and Computing 28 5 ( 2019 ) 696-719.","DOI":"10.1017\/S0963548319000105"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-016-0725-1"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"crossref","unstructured":"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.  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.","DOI":"10.1002\/rsa.20569"},{"key":"e_1_3_2_1_7_1","volume-title":"Eficient sampling and counting algorithms for the Potts model on Zd at all temperatures. arXiv preprint arXiv","author":"Borgs C","year":"1909","unstructured":"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 ). 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 )."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-010-0329-0"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"crossref","unstructured":"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.  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.","DOI":"10.1007\/BF01238860"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01017971"},{"key":"e_1_3_2_1_11_1","volume-title":"Counting independent sets in unbalanced bipartite graphs. arXiv preprint arXiv","author":"Cannon Sarah","year":"1906","unstructured":"Sarah Cannon and Will Perkins . 2019. Counting independent sets in unbalanced bipartite graphs. arXiv preprint arXiv : 1906 . 01666 ( 2019 ). Sarah Cannon and Will Perkins. 2019. Counting independent sets in unbalanced bipartite graphs. arXiv preprint arXiv: 1906. 01666 ( 2019 )."},{"key":"e_1_3_2_1_12_1","volume-title":"Zeros and approximations of Holant polynomials on the complex plane. arXiv preprint arXiv","author":"Casel Katrin","year":"1905","unstructured":"Katrin Casel , Philipp Fischbeck , Tobias Friedrich , Andreas G\u00f6bel , and JA Lagodzinski . 2019. Zeros and approximations of Holant polynomials on the complex plane. arXiv preprint arXiv : 1905 . 03194 ( 2019 ). Katrin Casel, Philipp Fischbeck, Tobias Friedrich, Andreas G\u00f6bel, and JA Lagodzinski. 2019. Zeros and approximations of Holant polynomials on the complex plane. arXiv preprint arXiv: 1905. 03194 ( 2019 )."},{"key":"e_1_3_2_1_13_1","volume-title":"Will Perkins, James Stewart, and Eric Vigoda.","author":"Chen Zongchen","year":"2019","unstructured":"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 . 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."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.84.066106"},{"key":"e_1_3_2_1_15_1","unstructured":"Hugo Duminil-Copin. 2017. Lectures on the Ising and Potts models on the hypercubic lattice. arXiv preprint arXiv:1707.00520 ( 2017 ).  Hugo Duminil-Copin. 2017. Lectures on the Ising and Potts models on the hypercubic lattice. arXiv preprint arXiv:1707.00520 ( 2017 )."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2019.189.1.2"},{"key":"e_1_3_2_1_17_1","volume-title":"Statistical mechanics of lattice systems: a concrete mathematical introduction","author":"Friedli Sacha","unstructured":"Sacha Friedli and Yvan Velenik . 2017. Statistical mechanics of lattice systems: a concrete mathematical introduction . Cambridge University Press . Sacha Friedli and Yvan Velenik. 2017. Statistical mechanics of lattice systems: a concrete mathematical introduction. Cambridge University Press."},{"key":"e_1_3_2_1_18_1","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"Galanis Andreas","unstructured":"Andreas Galanis , Qi Ge , Daniel \u0160tefankovi\u010d , 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. Andreas Galanis, Qi Ge, Daniel \u0160tefankovi\u010d, 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."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/140997580"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/140989728"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"crossref","unstructured":"Reza Gheissari and Eyal Lubetzky. 2018. Mixing Times of Critical TwoDimensional Potts Models. Communications on Pure and Applied Mathematics 71 5 ( 2018 ) 994-1046.  Reza Gheissari and Eyal Lubetzky. 2018. Mixing Times of Critical TwoDimensional Potts Models. Communications on Pure and Applied Mathematics 71 5 ( 2018 ) 994-1046.","DOI":"10.1002\/cpa.21718"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Reza Gheissari and Eyal Lubetzky. 2020. Quasi-polynomial mixing of critical two-dimensional random cluster models. Random Structures & Algorithms 56 2 ( 2020 ) 517-556.  Reza Gheissari and Eyal Lubetzky. 2020. Quasi-polynomial mixing of critical two-dimensional random cluster models. Random Structures & Algorithms 56 2 ( 2020 ) 517-556.","DOI":"10.1002\/rsa.20868"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2371656.2371660"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"crossref","unstructured":"C Gruber and H Kunz. 1971. General properties of polymer systems. Communications in Mathematical Physics 22 2 ( 1971 ) 133-161.  C Gruber and H Kunz. 1971. General properties of polymer systems. Communications in Mathematical Physics 22 2 ( 1971 ) 133-161.","DOI":"10.1007\/BF01651334"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"crossref","unstructured":"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.  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.","DOI":"10.1214\/17-AAP1335"},{"key":"e_1_3_2_1_26_1","volume-title":"to appear. An extended abstract appeared at STOC","author":"Helmuth Tyler","year":"2019","unstructured":"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.). 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.)."},{"key":"e_1_3_2_1_27_1","volume-title":"Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019 ). SIAM, 2235-2247","author":"Jenssen Matthew","year":"2019","unstructured":"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 . 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."},{"key":"e_1_3_2_1_28_1","series-title":"SIAM Journal on computing 22, 5 ( 1993 ), 1087-1116","volume-title":"Polynomial-time approximation algorithms for the Ising model","author":"Jerrum Mark","unstructured":"Mark Jerrum and Alistair Sinclair . 1993. Polynomial-time approximation algorithms for the Ising model . SIAM Journal on computing 22, 5 ( 1993 ), 1087-1116 . Mark Jerrum and Alistair Sinclair. 1993. Polynomial-time approximation algorithms for the Ising model. SIAM Journal on computing 22, 5 ( 1993 ), 1087-1116."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"crossref","unstructured":"Roman Koteck\u00fd and David Preiss. 1986. Cluster expansion for abstract polymer models. Communications in Mathematical Physics 103 3 ( 1986 ) 491-498.  Roman Koteck\u00fd and David Preiss. 1986. Cluster expansion for abstract polymer models. Communications in Mathematical Physics 103 3 ( 1986 ) 491-498.","DOI":"10.1007\/BF01211762"},{"key":"e_1_3_2_1_30_1","volume-title":"and SB Shlosman","author":"Kotecky Roman","year":"1982","unstructured":"Roman Kotecky ` and SB Shlosman . 1982 . First-order phase transitions in large entropy lattice models. Communications in Mathematical Physics 83, 4 ( 1982 ), 493-515. Roman Kotecky` and SB Shlosman. 1982. First-order phase transitions in large entropy lattice models. Communications in Mathematical Physics 83, 4 ( 1982 ), 493-515."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0703685104"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"crossref","unstructured":"Lahoussine Laanait Alain Messager Salvador Miracle-Sol\u00e9 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.  Lahoussine Laanait Alain Messager Salvador Miracle-Sol\u00e9 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.","DOI":"10.1007\/BF02099291"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRev.87.410"},{"key":"e_1_3_2_1_34_1","volume-title":"Counting independent sets and colorings on random regular bipartite graphs. arXiv preprint arXiv","author":"Liao Chao","year":"1903","unstructured":"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 ). 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 )."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"crossref","unstructured":"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.  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.","DOI":"10.1007\/BF02099735"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1101003"},{"key":"e_1_3_2_1_37_1","volume-title":"Rigidity of proper colorings of Zd. arXiv preprint arXiv","author":"Peled Ron","year":"1808","unstructured":"Ron Peled and Yinon Spinka . 2018. Rigidity of proper colorings of Zd. arXiv preprint arXiv : 1808 . 03597 ( 2018 ). Ron Peled and Yinon Spinka. 2018. Rigidity of proper colorings of Zd. arXiv preprint arXiv: 1808. 03597 ( 2018 )."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"crossref","unstructured":"Sergey Anatol'evich Pirogov and Ya G Sinai. 1975. Phase diagrams of classical lattice systems. Theoretical and Mathematical Physics 25 3 ( 1975 ) 1185-1192.  Sergey Anatol'evich Pirogov and Ya G Sinai. 1975. Phase diagrams of classical lattice systems. Theoretical and Mathematical Physics 25 3 ( 1975 ) 1185-1192.","DOI":"10.1007\/BF01040127"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.34"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1214\/13-AOP888"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516512.1516520"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"crossref","unstructured":"Mario Ullrich. 2013. Comparison of Swendsen-Wang and heat-bath dynamics. Random Structures & Algorithms 42 4 ( 2013 ) 520-535.  Mario Ullrich. 2013. Comparison of Swendsen-Wang and heat-bath dynamics. Random Structures & Algorithms 42 4 ( 2013 ) 520-535.","DOI":"10.1002\/rsa.20431"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132538"}],"event":{"name":"STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing","location":"Chicago IL USA","acronym":"STOC '20","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384271","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384271","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:41:12Z","timestamp":1750185672000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384271"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":43,"alternative-id":["10.1145\/3357713.3384271","10.1145\/3357713"],"URL":"https:\/\/doi.org\/10.1145\/3357713.3384271","relation":{},"subject":[],"published":{"date-parts":[[2020,6,22]]},"assertion":[{"value":"2020-06-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}