Abstract: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(\beta_{\max})}/{Z(\beta_{\min})}$ between partition functions $Z(\beta)=\sum_{x\in \Omega} \exp(\beta H(x))$ of Gibbs distributions $\mu_\beta$ over $\Omega$ with Hamiltonian $H$, given access to a sampling oracle that produces samples from $\mu_\beta$ for $\beta \in [\beta_{\min}, \beta_{\max}]$.
The best bound achieved by known annealing algorithms with relative error $\varepsilon$ is $O(q \log h / \varepsilon^2)$, where $q, h$ are parameters which respectively bound $\ln Q$ and $H$. However, all known algorithms attaining this near-optimal complexity are inherently sequential, or *adaptive*: the queried parameters $\beta$ depend on previous samples.
We develop a simple non-adaptive algorithm for approximate counting using $O(q \log^2 h / \varepsilon^2)$ samples, as well as an algorithm that achieves $O(q \log h / \varepsilon^2)$ samples with just two rounds of adaptivity, matching the best sample complexity of sequential algorithms. These algorithms naturally give rise to work-efficient parallel (RNC) counting algorithms.
We discuss applications to RNC counting algorithms for several classic models, including the anti-ferromagnetic 2-spin, monomer-dimer and ferromagnetic Ising models.
From: David Harris [view email]
[v1]
Wed, 1 Apr 2026 13:27:39 UTC (28 KB)
[v2]
Sun, 12 Jul 2026 00:29:26 UTC (31 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。