Near-Optimal Parallel Approximate Counting via Sampling

David G. Harris, Vladimir Kolmogorov, Hongyang Liu, Yitong Yin, Yiyao Zhang

arXivarxiv/2604.01263Apr 1, 2026cs.DSscore 0

The computational equivalence between approximate counting and sampling is well established for polynomial-time algorithms. The most efficient general reduction from counting to sampling is achieved via simulated annealing, where the counting problem is formulated in terms of estimating the ratio $Q={Z(β_{\max})}/{Z(β_{\min})}$ between partition functions $Z(β)=\sum_{x\in Ω} \exp(βH(x))$ of Gibbs distributions $μ_β$ over $Ω$ with Hamiltonian $H$, given access to a sampling oracle that produces samples from $μ_β$ for $β\in [β_{\min}, β_{\max}]$. The best bound achieved by known annealing…

SourceJSON

Comments and reviews

No comments yet.

API

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