# Subquadratic Counting via Perfect Marginal Sampling

arXiv: https://arxiv.org/abs/2604.02235 · HTML: https://mlsanity.com/paper/2604.02235/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Apr 2026.

## Built on by (most cited first, 1 of 1)

- [Learning mathsfAC0 under Locally Sampleable Graphical Models](https://mlsanity.com/paper/2607.08303/) (2026)

## Abstract (arXiv)

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.