{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,29]],"date-time":"2025-12-29T11:42:24Z","timestamp":1767008544344,"version":"3.41.0"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2015,12,10]],"date-time":"2015-12-10T00:00:00Z","timestamp":1449705600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100006435","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1217458 and CCF-1318374"],"award-info":[{"award-number":["CCF-1217458 and CCF-1318374"]}],"id":[{"id":"10.13039\/100006435","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["334828"],"award-info":[{"award-number":["334828"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2015,12,10]]},"abstract":"<jats:p>A remarkable connection has been established for antiferromagnetic 2-spin systems, including the Ising and hard-core models, showing that the computational complexity of approximating the partition function for graphs with maximum degree \u0394 undergoes a phase transition that coincides with the statistical physics uniqueness\/nonuniqueness phase transition on the infinite \u0394-regular tree. Despite this clear picture for 2-spin systems, there is little known for multispin systems. We present the first analog of this in approximability results for multispin systems.<\/jats:p>\n          <jats:p>The main difficulty in previous inapproximability results was analyzing the behavior of the model on random \u0394-regular bipartite graphs, which served as the gadget in the reduction. To this end, one needs to understand the moments of the partition function. Our key contribution is connecting: (i) induced matrix norms, (ii) maxima of the expectation of the partition function, and (iii) attractive fixed points of the associated tree recursions (belief propagation). The view through matrix norms allows a simple and generic analysis of the second moment for any spin system on random \u0394-regular bipartite graphs. This yields concentration results for any spin system in which one can analyze the maxima of the first moment. The connection to fixed points of the tree recursions enables an analysis of the maxima of the first moment for specific models of interest.<\/jats:p>\n          <jats:p>\n            For\n            <jats:italic>k<\/jats:italic>\n            -colorings we prove that for even\n            <jats:italic>k<\/jats:italic>\n            , in a tree nonuniqueness region (which corresponds to\n            <jats:italic>k<\/jats:italic>\n            &lt; \u0394) there is no FPRAS, unless NP = RP, to approximate the number of colorings for triangle-free \u0394-regular graphs. Our proof extends to the antiferromagnetic Potts model, and, in fact, to every antiferromagnetic model under a mild condition.\n          <\/jats:p>","DOI":"10.1145\/2785964","type":"journal-article","created":{"date-parts":[[2015,12,14]],"date-time":"2015-12-14T14:19:41Z","timestamp":1450102781000},"page":"1-60","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":39,"title":["Inapproximability for Antiferromagnetic Spin Systems in the Tree Nonuniqueness Region"],"prefix":"10.1145","volume":"62","author":[{"given":"Andreas","family":"Galanis","sequence":"first","affiliation":[{"name":"University of Oxford"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"\u0160tefankovi\u010d","sequence":"additional","affiliation":[{"name":"University of Rochester"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eric","family":"Vigoda","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,12,10]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/648256.752884"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1215\/S0012-7094-77-04426-X"},{"key":"e_1_2_2_3_1","volume-title":"Bolyai Soc. Math. Stud.","volume":"10","author":"Brightwell G. R.","unstructured":"G. R. Brightwell and P. Winkler . 2002. Random colorings of a Cayley tree. In Contemporary Combinatorics , Bolyai Soc. Math. Stud. , Vol. 10 . J\u00e1nos Bolyai Math. Soc., Budapest, 247--276. G. R. Brightwell and P. Winkler. 2002. Random colorings of a Cayley tree. In Contemporary Combinatorics, Bolyai Soc. Math. Stud., Vol. 10. J\u00e1nos Bolyai Math. Soc., Budapest, 247--276."},{"key":"e_1_2_2_4_1","volume-title":"Asymptotic Methods in Analysis","author":"de Bruijn N. G.","unstructured":"N. G. de Bruijn . 1981. Asymptotic Methods in Analysis ( 3 rd ed.). Dover Publications, Inc. , New York . xii &plus; 200 pages. N. G. de Bruijn. 1981. Asymptotic Methods in Analysis (3rd ed.). Dover Publications, Inc., New York. xii &plus; 200 pages.","edition":"3"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20479"},{"key":"e_1_2_2_6_1","volume-title":"Inapproximability of the partition function for the antiferromagnetic Ising and hard-core models. CoRR abs\/1203.2226","author":"Galanis Andreas","year":"2012","unstructured":"Andreas Galanis , Daniel \u0160tefankovi\u010d , and Eric Vigoda . 2012. Inapproximability of the partition function for the antiferromagnetic Ising and hard-core models. CoRR abs\/1203.2226 ( 2012 ). Andreas Galanis, Daniel \u0160tefankovi\u010d, and Eric Vigoda. 2012. Inapproximability of the partition function for the antiferromagnetic Ising and hard-core models. CoRR abs\/1203.2226 (2012)."},{"key":"e_1_2_2_7_1","volume-title":"Gibbs Measures and Phase Transitions","author":"Georgii Hans-Otto","unstructured":"Hans-Otto Georgii . 2011. Gibbs Measures and Phase Transitions ( 2 nd ed.). de Gruyter Studies in Mathematics, Vol. 9 . Walter de Gruyter & Co. , Berlin. xiv &plus;&plus; 545 pages. Hans-Otto Georgii. 2011. Gibbs Measures and Phase Transitions (2nd ed.). de Gruyter Studies in Mathematics, Vol. 9. Walter de Gruyter & Co., Berlin. xiv &plus;&plus; 545 pages.","edition":"2"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10090"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00001601"},{"key":"e_1_2_2_10_1","volume-title":"Johnson","author":"Horn Roger A.","year":"2013","unstructured":"Roger A. Horn and Charles R . Johnson . 2013 . Matrix Analysis (2nd ed.). Cambridge University Press , Cambridge. xviii &plus; 643 pages. Roger A. Horn and Charles R. Johnson. 2013. Matrix Analysis (2nd ed.). Cambridge University Press, Cambridge. xviii &plus; 643 pages."},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300001735"},{"volume-title":"Random Graphs","author":"Janson Svante","key":"e_1_2_2_12_1","unstructured":"Svante Janson , Tomasz Luczak , and Andrzej Rucinski . 2000. Random Graphs . Wiley-Interscience , New York . xii &plus; 333 pages. Svante Janson, Tomasz Luczak, and Andrzej Rucinski. 2000. Random Graphs. Wiley-Interscience, New York. xii &plus; 333 pages."},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-7152(02)00054-8"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1177005872"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627817.2627822"},{"key":"e_1_2_2_17_1","volume-title":"Luenberger and Yinyu Ye","author":"David","year":"2008","unstructured":"David G. Luenberger and Yinyu Ye . 2008 . Linear and Nonlinear Programming (3rd ed.). Springer , New York. xiv &plus; 546 pages. David G. Luenberger and Yinyu Ye. 2008. Linear and Nonlinear Programming (3rd ed.). Springer, New York. xiv &plus; 546 pages."},{"volume-title":"Graph colouring and the probabilistic method. Algorithms and Combinatorics, 23","author":"Molloy Michael","key":"e_1_2_2_18_1","unstructured":"Michael Molloy and Bruce Reed . 2002. Graph colouring and the probabilistic method. Algorithms and Combinatorics, 23 . Springer-Verlag , Berlin . xiv &plus; 326 pages. Michael Molloy and Bruce Reed. 2002. Graph colouring and the probabilistic method. Algorithms and Combinatorics, 23. Springer-Verlag, Berlin. xiv &plus; 326 pages."},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380840"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1667053.1667060"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-007-0131-9"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240050209"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095191"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.34"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.56"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132538"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2785964","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2785964","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:43:14Z","timestamp":1750225394000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2785964"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,12,10]]},"references-count":25,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2015,12,10]]}},"alternative-id":["10.1145\/2785964"],"URL":"https:\/\/doi.org\/10.1145\/2785964","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2015,12,10]]},"assertion":[{"value":"2014-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-12-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}