Subquadratic Counting via Perfect Marginal Sampling

We study the computational complexity of approximately computing the partition function of a spin system. Techniques based on standard counting-to-sampling reductions yield tildeO(n2)-time algorithms, where n is the size of the input graph. We present new counting algorithms that break the quadratic-time barrier in a wide range of settings. For example, for the hardcore model of λ-weighted independent sets in graphs of maximum degree Delta, we obtain a tildeO(n2-δ)-time approximate counting algorithm, for some constant δ > 0, when the fugacity λ < frac1Delta-1, improving over the previous regime of λ = o(Delta-3/2) by Anand, Feng, Freifeld, Guo, and Wang (2025). Our results apply broadly to many other spin systems, such as the Ising model, hypergraph independent sets, and vertex colorings. Interestingly, our work reveals a deep connection between textitsubquadratic counting and textitperfect marginal sampling. For two-spin systems such as the hardcore and Ising models, we show that the existence of perfect marginal samplers directly yields subquadratic counting algorithms in a textitblack-box fashion. For general spin systems, we show that almost all existing perfect marginal samplers can be adapted to produce a sufficiently low-variance marginal estimator in sublinear time, leading to subquadratic counting algorithms.