{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,7]],"date-time":"2026-08-07T22:50:01Z","timestamp":1786143001231,"version":"3.56.0"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2012,10,1]],"date-time":"2012-10-01T00:00:00Z","timestamp":1349049600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2012,10]]},"abstract":"<jats:p>\n            We provide evidence that it is computationally difficult to approximate the partition function of the ferromagnetic\n            <jats:italic>q<\/jats:italic>\n            -state Potts model when\n            <jats:italic>q<\/jats:italic>\n            &gt; 2. Specifically, we show that the partition function is hard for the complexity class #RHPi under approximation-preserving reducibility. Thus, it is as hard to approximate the partition function as it is to find approximate solutions to a wide range of counting problems, including that of determining the number of independent sets in a bipartite graph. Our proof exploits the first-order phase transition of the \u201crandom cluster\u201d model, which is a probability distribution on graphs that is closely related to the\n            <jats:italic>q<\/jats:italic>\n            -state Potts model.\n          <\/jats:p>","DOI":"10.1145\/2371656.2371660","type":"journal-article","created":{"date-parts":[[2012,11,13]],"date-time":"2012-11-13T15:03:58Z","timestamp":1352819038000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":48,"title":["Approximating the partition function of the ferromagnetic Potts model"],"prefix":"10.1145","volume":"59","author":[{"given":"Leslie Ann","family":"Goldberg","sequence":"first","affiliation":[{"name":"University of Liverpool, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mark","family":"Jerrum","sequence":"additional","affiliation":[{"name":"Queen Mary, University of London, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2012,11,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240060409"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01213683"},{"key":"e_1_2_1_3_1","series-title":"Lecture Notes in Computer Science Series","volume-title":"On the approximation complexity hierarchy","author":"Bordewich M."},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS'99)","author":"Borgs C."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1088\/1751-8113\/40\/46\/001"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.43410"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.02.029"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-1(1:5)2005"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1073-y"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0031-8914(72)90045-6"},{"key":"e_1_2_1_11_1","volume-title":"IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS'10)","volume":"8","author":"Ge Q.","year":"2010"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1017\/S096354830600767X"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2008.04.003"},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Goldberg L.\n     and \n      Jerrum M\n  . \n  2010\n  . Approximating the partition function of the ferromagnetic Potts model. In Automata Languages and Programming S. Abramsky C. Gavoille C. Kirchner F. Meyer auf der Heide and P. Spirakis Eds. Lecture Notes in Computer Science Series vol. \n  6198 Springer Berlin\/Heidelberg 396--407.   Goldberg L. and Jerrum M. 2010. Approximating the partition function of the ferromagnetic Potts model. In Automata Languages and Programming S. Abramsky C. Gavoille C. Kirchner F. Meyer auf der Heide and P. Spirakis Eds. Lecture Notes in Computer Science Series vol. 6198 Springer Berlin\/Heidelberg 396--407.","DOI":"10.1007\/978-3-642-14165-2_34"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1214\/ECP.v17-1712"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Goldberg L. A. and Jerrum M. 2012b. Inapproximability of the Tutte polynomial of a planar graph. Computat. Complex. To Appear.  Goldberg L. A. and Jerrum M. 2012b. Inapproximability of the Tutte polynomial of a planar graph. Computat. Complex. To Appear.","DOI":"10.1007\/s00037-012-0046-4"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1004610900745"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02186281"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01645980"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2009.03.002"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100068936"},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Janson S. \u0141uczak T. and Rucinski A. 2000. Random Graphs. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience New York.  Janson S. \u0141uczak T. and Rucinski A. 2000. Random Graphs. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience New York.","DOI":"10.1002\/9781118032718"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222066"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/11534.11537"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.v28:2"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100027419"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.34"},{"key":"e_1_2_1_29_1","volume-title":"Surveys in Combinatorics","author":"Sokal A."},{"key":"e_1_2_1_30_1","series-title":"Encyclopedia of Mathematics and its Applications Series","volume-title":"Graph Theory","author":"Tutte W. T."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704446797"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300000195"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511752506"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266407"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2371656.2371660","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2371656.2371660","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:21:18Z","timestamp":1750238478000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2371656.2371660"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,10]]},"references-count":33,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2012,10]]}},"alternative-id":["10.1145\/2371656.2371660"],"URL":"https:\/\/doi.org\/10.1145\/2371656.2371660","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,10]]},"assertion":[{"value":"2010-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-11-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}