{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T00:41:46Z","timestamp":1777596106741,"version":"3.51.4"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T00:00:00Z","timestamp":1630454400000},"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":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2021,12,31]]},"abstract":"<jats:p>A spin system is a framework in which the vertices of a graph are assigned spins from a finite set. The interactions between neighbouring spins give rise to weights, so a spin assignment can also be viewed as a weighted graph homomorphism. The problem of approximating the partition function (the aggregate weight of spin assignments) or of sampling from the resulting probability distribution is typically intractable for general graphs.<\/jats:p>\n          <jats:p>\n            In this work, we consider arbitrary spin systems on bipartite expander \u0394-regular graphs, including the canonical class of bipartite random \u0394-regular graphs. We develop fast approximate sampling and counting algorithms for general spin systems whenever the degree and the spectral gap of the graph are sufficiently large. Roughly, this guarantees that the spin system is in the so-called low-temperature regime. Our approach generalises the techniques of Jenssen et\u00a0al. and Chen et\u00a0al. by showing that typical configurations on bipartite expanders correspond to \u201cbicliques\u201d of the spin system; then, using suitable polymer models, we show how to sample such configurations and approximate the partition function in \u00d5(\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            ) time, where\n            <jats:italic>n<\/jats:italic>\n            is the size of the graph.\n          <\/jats:p>","DOI":"10.1145\/3470865","type":"journal-article","created":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T19:28:46Z","timestamp":1630524526000},"page":"1-18","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Fast Algorithms for General Spin Systems on Bipartite Expanders"],"prefix":"10.1145","volume":"13","author":[{"given":"Andreas","family":"Galanis","sequence":"first","affiliation":[{"name":"University of Oxford, Oxford, UK"}]},{"given":"Leslie Ann","family":"Goldberg","sequence":"additional","affiliation":[{"name":"University of Oxford, Oxford, UK"}]},{"given":"James","family":"Stewart","sequence":"additional","affiliation":[{"name":"University of Oxford, Oxford, UK"}]}],"member":"320","published-online":{"date-parts":[[2021,9]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"G. Brito I. Dumitriu and K. D. Harris. 2018. Spectral gap in random bipartite biregular graphs and applications. arXiv:1804.07808.  G. Brito I. Dumitriu and K. D. Harris. 2018. Spectral gap in random bipartite biregular graphs and applications. arXiv:1804.07808."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.011"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2015.11.009"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.88"},{"key":"e_1_2_1_5_1","unstructured":"C. Carlson E. Davies and A. Kolla. 2020. Efficient algorithms for the Potts model on small-set expanders. arXiv:2003.01154.  C. Carlson E. Davies and A. Kolla. 2020. Efficient algorithms for the Potts model on small-set expanders. arXiv:2003.01154."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20968"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.37236\/2831"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1002\/1098-2418(200010\/12)17:3\/4<260::AID-RSA5>3.0.CO;2-W"},{"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.1137\/15M1020551"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2785964"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/140997580"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2371656.2371660"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2600917"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702408363"},{"key":"e_1_2_1_16_1","unstructured":"A. Govorov J.-Y. Cai and M. Dyer. 2020. A dichotomy for bounded degree graph homomorphisms with nonnegative weights. arXiv:2002.02021.  A. Govorov J.-Y. Cai and M. Dyer. 2020. A dichotomy for bounded degree graph homomorphisms with nonnegative weights. arXiv:2002.02021."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01651334"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(95)00199-2"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-019-00928-y"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-06-01126-8"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201919)","author":"Jenssen M.","unstructured":"M. Jenssen , P. Keevash , and W. Perkins . 2019. Algorithms for #BIS-hard problems on expander graphs . In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201919) . 2235\u20132247. M. Jenssen, P. Keevash, and W. Perkins. 2019. Algorithms for #BIS-hard problems on expander graphs. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201919). 2235\u20132247."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/210118.210136"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01211762"},{"key":"e_1_2_1_24_1","volume-title":"Leibniz International Proceedings in Informatics","volume":"145","author":"Liao C.","unstructured":"C. Liao , J. Lin , P. Lu , and Z. Mao . 2019. Counting independent sets and colorings on random regular bipartite graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM\u201919) . Leibniz International Proceedings in Informatics , Vol. 145 . Article 34, 12 pages. C. Liao, J. Lin, P. Lu, and Z. Mao. 2019. Counting independent sets and colorings on random regular bipartite graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM\u201919). Leibniz International Proceedings in Informatics, Vol. 145. Article 34, 12 pages."},{"key":"e_1_2_1_25_1","article-title":"Counting in two-spin models on -regular graphs","volume":"42","author":"Sly A.","year":"2014","unstructured":"A. Sly and N. Sun . 2014 . Counting in two-spin models on -regular graphs . Annals of Probabability 42 , 6 (11 2014), 2383\u20132416. A. Sly and N. Sun. 2014. Counting in two-spin models on -regular graphs. Annals of Probabability 42, 6 (11 2014), 2383\u20132416.","journal-title":"Annals of Probabability"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/0605030"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3470865","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3470865","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:18:55Z","timestamp":1750191535000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3470865"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9]]},"references-count":26,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,12,31]]}},"alternative-id":["10.1145\/3470865"],"URL":"https:\/\/doi.org\/10.1145\/3470865","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,9]]},"assertion":[{"value":"2020-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-09-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}