{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,1]],"date-time":"2026-03-01T06:32:54Z","timestamp":1772346774890,"version":"3.50.1"},"reference-count":33,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2016,2,2]],"date-time":"2016-02-02T00:00:00Z","timestamp":1454371200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2016,7]]},"abstract":"<jats:p>Recent inapproximability results of Sly (2010), together with an approximation algorithm presented by Weitz (2006), establish a beautiful picture of the computational complexity of approximating the partition function of the hard-core model. Let \u03bb<jats:sub><jats:italic>c<\/jats:italic><\/jats:sub>(<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548315000401_inline1\"\/><jats:tex-math>$\\mathbb{T}_{\\Delta}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>) denote the critical activity for the hard-model on the infinite \u0394-regular tree. Weitz presented an<jats:monospace>FPTAS<\/jats:monospace>for the partition function when \u03bb &lt; \u03bb<jats:sub><jats:italic>c<\/jats:italic><\/jats:sub>(<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548315000401_inline1\"\/><jats:tex-math>$\\mathbb{T}_{\\Delta}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>) for graphs with constant maximum degree \u0394. In contrast, Sly showed that for all \u0394 \u2a7e 3, there exists \u03b5<jats:sub>\u0394<\/jats:sub>&gt; 0 such that (unless RP = NP) there is no<jats:monospace>FPRAS<\/jats:monospace>for approximating the partition function on graphs of maximum degree \u0394 for activities \u03bb satisfying \u03bb<jats:sub><jats:italic>c<\/jats:italic><\/jats:sub>(<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548315000401_inline1\"\/><jats:tex-math>$\\mathbb{T}_{\\Delta}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>) &lt; \u03bb &lt; \u03bb<jats:sub><jats:italic>c<\/jats:italic><\/jats:sub>(<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548315000401_inline1\"\/><jats:tex-math>$\\mathbb{T}_{\\Delta}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>) + \u03b5<jats:sub>\u0394<\/jats:sub>.<\/jats:p><jats:p>We prove that a similar phenomenon holds for the antiferromagnetic Ising model. Sinclair, Srivastava and Thurley (2014) extended Weitz's approach to the antiferromagnetic Ising model, yielding an<jats:monospace>FPTAS<\/jats:monospace>for the partition function for all graphs of constant maximum degree \u0394 when the parameters of the model lie in the uniqueness region of the infinite \u0394-regular tree. We prove the complementary result for the antiferromagnetic Ising model without external field, namely, that unless RP = NP, for all \u0394 \u2a7e 3, there is no<jats:monospace>FPRAS<\/jats:monospace>for approximating the partition function on graphs of maximum degree \u0394 when the inverse temperature lies in the non-uniqueness region of the infinite tree<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548315000401_inline1\"\/><jats:tex-math>$\\mathbb{T}_{\\Delta}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. Our proof works by relating certain second moment calculations for random \u0394-regular bipartite graphs to the tree recursions used to establish the critical points on the infinite tree.<\/jats:p>","DOI":"10.1017\/s0963548315000401","type":"journal-article","created":{"date-parts":[[2016,2,2]],"date-time":"2016-02-02T09:32:04Z","timestamp":1454405524000},"page":"500-559","source":"Crossref","is-referenced-by-count":80,"title":["Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models"],"prefix":"10.1017","volume":"25","author":[{"given":"ANDREAS","family":"GALANIS","sequence":"first","affiliation":[]},{"given":"DANIEL","family":"\u0160TEFANKOVI\u010c","sequence":"additional","affiliation":[]},{"given":"ERIC","family":"VIGODA","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2016,2,2]]},"reference":[{"key":"S0963548315000401_ref27","doi-asserted-by":"crossref","unstructured":"Sly A. (2010) Computational transition at the uniqueness threshold. In Proc. 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 287\u2013296.","DOI":"10.1109\/FOCS.2010.34"},{"key":"S0963548315000401_ref29","volume-title":"Spin Glasses: A Challenge for Mathematicians","author":"Talagrand","year":"2003"},{"key":"S0963548315000401_ref7","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701383844"},{"key":"S0963548315000401_ref25","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-012-0421-8"},{"key":"S0963548315000401_ref21","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198570837.001.0001"},{"key":"S0963548315000401_ref1","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2005.162.1335"},{"key":"S0963548315000401_ref15","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032718"},{"key":"S0963548315000401_ref16","doi-asserted-by":"publisher","DOI":"10.1137\/0222066"},{"key":"S0963548315000401_ref6","doi-asserted-by":"publisher","DOI":"10.1214\/12-AOP828"},{"key":"S0963548315000401_ref12","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10090"},{"key":"S0963548315000401_ref23","doi-asserted-by":"crossref","unstructured":"Mossel E. (2004) Survey: Information flow on trees. In Graphs, Morphisms, and Statistical Physics, Vol. 63 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pp. 155\u2013170.","DOI":"10.1090\/dimacs\/063\/12"},{"key":"S0963548315000401_ref4","volume-title":"Asymptotic Methods in Analysis","author":"de Bruijn","year":"1981"},{"key":"S0963548315000401_ref22","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199705)10:3<305::AID-RSA1>3.0.CO;2-#"},{"key":"S0963548315000401_ref24","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-007-0131-9"},{"key":"S0963548315000401_ref9","unstructured":"Galanis A. , \u0160tefankovi\u010d D. and Vigoda E. (2012) Inapproximability of the partition function for the antiferromagnetic Ising and hard-core models. arXiv.org:1203.2226"},{"key":"S0963548315000401_ref31","doi-asserted-by":"crossref","unstructured":"Weitz D. (2006) Counting independent sets up to the tree threshold. In Proc. 38th Annual ACM Symposium on Theory of Computing (STOC), pp. 140\u2013149.","DOI":"10.1145\/1132516.1132538"},{"key":"S0963548315000401_ref28","doi-asserted-by":"publisher","DOI":"10.1214\/13-AOP888"},{"key":"S0963548315000401_ref10","doi-asserted-by":"crossref","unstructured":"Galanis A. , \u0160tefankovi\u010d D. and Vigoda E. (2014) Inapproximability for antiferromagnetic spin systems in the tree non-uniqueness region. In Proc. 46th Annual ACM Symposium on Theory of Computing (STOC). 62 pp. 823\u2013831. http:\/\/dl.acm.org\/citation.cfm?doid=2785964","DOI":"10.1145\/2591796.2591878"},{"key":"S0963548315000401_ref26","doi-asserted-by":"publisher","DOI":"10.1007\/s10955-014-0947-5"},{"key":"S0963548315000401_ref19","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-004-1147-y"},{"key":"S0963548315000401_ref33","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2011.04.012"},{"key":"S0963548315000401_ref13","doi-asserted-by":"publisher","DOI":"10.1007\/PL00001601"},{"key":"S0963548315000401_ref17","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1111\/j.2517-6161.1985.tb01367.x","article-title":"Stochastic models of computer communication systems.","volume":"47","author":"Kelly","year":"1985","journal-title":"J. Royal Statist. Soc. Ser. B"},{"key":"S0963548315000401_ref2","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-04-00464-3"},{"key":"S0963548315000401_ref32","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511721335.010"},{"key":"S0963548315000401_ref20","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20132"},{"key":"S0963548315000401_ref5","unstructured":"Cai J.-Y. , Galanis A. , Goldberg L. A. , Guo H. , Jerrum M. , \u0160tefankovi\u010d D. and Vigoda E. (2014) #BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region. In Proc. 18th International Workshop on Randomization and Computation (RANDOM), pp. 582\u2013595."},{"key":"S0963548315000401_ref11","volume-title":"De Gruyter Studies in Mathematics","author":"Georgii","year":"1988"},{"key":"S0963548315000401_ref3","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-011-0353-8"},{"key":"S0963548315000401_ref30","doi-asserted-by":"publisher","DOI":"10.1137\/0208032"},{"key":"S0963548315000401_ref14","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300001735"},{"key":"S0963548315000401_ref18","doi-asserted-by":"crossref","unstructured":"Li L. , Lu P. and Yin Y. (2013) Correlation decay up to uniqueness in spin systems. In Proc. 24th Annual ACM\u2013SIAM Symposium on Discrete Algorithms (SODA), pp. 47\u201366.","DOI":"10.1137\/1.9781611973105.5"},{"key":"S0963548315000401_ref8","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20479"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548315000401","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,14]],"date-time":"2024-06-14T03:25:08Z","timestamp":1718335508000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548315000401\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,2,2]]},"references-count":33,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,7]]}},"alternative-id":["S0963548315000401"],"URL":"https:\/\/doi.org\/10.1017\/s0963548315000401","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,2,2]]}}}