Subquadratic Counting via Perfect Marginal Sampling

Xiaoyu Chen; Zongchen Chen; Kuikui Liu; Xinyuan Zhang

Subquadratic Counting via Perfect Marginal Sampling

Xiaoyu Chen, Zongchen Chen, Kuikui Liu, Xinyuan Zhang

arXivarxiv/2604.02235Apr 2, 2026cs.DSscore 0

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…

Source JSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2604.02235
curl -X POST /api/v1/records/arxiv/2604.02235/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2604.02235/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'