{"id":"arxiv/2604.02235","url":"https://arxiv.org/abs/2604.02235","tags":["cs.DS","math.PR"],"score":0,"title":"Subquadratic Counting via Perfect Marginal Sampling","domain":"cs.DS","source":"arxiv","authors":["Xiaoyu Chen","Zongchen Chen","Kuikui Liu","Xinyuan Zhang"],"reviews":0,"subject":"cs.DS","summary":"We study the computational complexity of approximately computing the partition function of a spin system. Techniques based on standard counting-to-sampling reductions yield $\\tilde{O}(n^2)$-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 $Δ$, we obtain a $\\tilde{O}(n^{2-δ})$-time approximate counting algorithm, for some constant $δ> 0$, when the fugacity $λ< \\frac{1}{Δ-1}$, improving…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-04-02","reactions":{}}