{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:29:28Z","timestamp":1750220968402,"version":"3.41.0"},"reference-count":15,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2019,7,23]],"date-time":"2019-07-23T00:00:00Z","timestamp":1563840000000},"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\/N004221\/1"],"award-info":[{"award-number":["EP\/N004221\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100011199","name":"European Research Council","doi-asserted-by":"publisher","award":["334828"],"award-info":[{"award-number":["334828"]}],"id":[{"id":"10.13039\/100011199","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2019,12,31]]},"abstract":"<jats:p>In the Ising model, we consider the problem of estimating the covariance of the spins at two specified vertices. In the ferromagnetic case, it is easy to obtain an additive approximation to this covariance by repeatedly sampling from the relevant Gibbs distribution. However, we desire a multiplicative approximation, and it is not clear how to achieve this by sampling, given that the covariance can be exponentially small. Our main contribution is a fully polynomial time randomised approximation scheme (FPRAS) for the covariance in the ferromagnetic case. We also show that the restriction to the ferromagnetic case is essential\u2014there is no FPRAS for multiplicatively estimating the covariance of an antiferromagnetic Ising model unless RP = #P. In fact, we show that even determining the sign of the covariance is #P-hard in the antiferromagnetic case.<\/jats:p>","DOI":"10.1145\/3337785","type":"journal-article","created":{"date-parts":[[2019,7,24]],"date-time":"2019-07-24T12:05:56Z","timestamp":1563969956000},"page":"1-20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Approximating Pairwise Correlations in the Ising Model"],"prefix":"10.1145","volume":"11","author":[{"given":"Leslie Ann","family":"Goldberg","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Oxford, Oxford, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mark","family":"Jerrum","sequence":"additional","affiliation":[{"name":"School of Mathematical Sciences, Queen Mary, University of London, London, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,7,23]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10955-016-1572-2"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1177005980"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevD.38.2009"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0031-8914(72)90045-6"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/12088330X"},{"volume-title":"The Random-Cluster Model. Grundlehren der Mathematischen Wissenschaften {Fundamental Principles of Mathematical Sciences}","author":"Grimmett Geoffrey","key":"e_1_2_1_6_1"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222066"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1008731.1008738"},{"volume-title":"Probability and Computing","author":"Mitzenmacher Michael","key":"e_1_2_1_9_1","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511813603"},{"volume-title":"Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201999)","year":"1999","author":"Randall Dana","key":"e_1_2_1_10_1"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/611397.611401"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300000390"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/0211027"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01342928"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300000195"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3337785","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3337785","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:54:25Z","timestamp":1750204465000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3337785"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,23]]},"references-count":15,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,12,31]]}},"alternative-id":["10.1145\/3337785"],"URL":"https:\/\/doi.org\/10.1145\/3337785","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2019,7,23]]},"assertion":[{"value":"2018-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-07-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}