Fast counting and sampling for ferromagnetic two-spin systems
Provides the first efficient sampling algorithm and improves estimation runtime for ferromagnetic two-spin systems, benefiting researchers in statistical physics and computer science.
The authors introduce new models for ferromagnetic two-spin systems, enabling efficient sampling and a near-quadratic-time algorithm for partition function approximation in regimes where no efficient sampling was previously known.
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).