{"ID":5936989,"CreatedAt":"2026-07-07T03:14:33.014478982Z","UpdatedAt":"2026-07-09T15:38:11.834581458Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.05248","arxiv_id":"2607.05248","title":"Fast counting and sampling for ferromagnetic two-spin systems","abstract":"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, and Lu (2020).","short_abstract":"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 system...","url_abs":"https://arxiv.org/abs/2607.05248","url_pdf":"https://arxiv.org/pdf/2607.05248v1","authors":"[\"Weiming Feng\",\"Heng Guo\",\"Yichun Yang\"]","published":"2026-07-06T15:56:56Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"math.PR\"]","methods":"[]","has_code":false}