{"id":"arxiv/2607.05248","url":"https://arxiv.org/abs/2607.05248","tags":["cs.DS","math.PR"],"score":0,"title":"Fast counting and sampling for ferromagnetic two-spin systems","domain":"cs.DS","source":"arxiv","authors":["Weiming Feng","Heng Guo","Yichun Yang"],"reviews":0,"subject":"cs.DS","summary":"We introduce two new models equivalent to ferromagnetic two-spin systems: a weighted subgraph model and a random cluster type model. Using these new connections, we obtain an efficient sampling algorithm and a new randomised algorithm that efficiently approximates the partition function of ferromagnetic two-spin systems in certain parameter regimes. No efficient sampling algorithms are known before in this regime, and our new estimation algorithm runs in near-quadratic time for bounded degree graphs and in polynomial time for general graphs, improving upon the previous algorithm of Guo, Liu,…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-07-06","reactions":{}}