{"id":"arxiv/2604.01263","url":"https://arxiv.org/abs/2604.01263","tags":["cs.DS","math.PR"],"score":0,"title":"Near-Optimal Parallel Approximate Counting via Sampling","domain":"cs.DS","source":"arxiv","authors":["David G. Harris","Vladimir Kolmogorov","Hongyang Liu","Yitong Yin","Yiyao Zhang"],"reviews":0,"subject":"cs.DS","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-04-01","reactions":{}}