Work-Efficient Parallel Counting via Sampling
This addresses the challenge of efficient parallel counting in computational statistics and physics, offering a significant improvement over prior methods by combining near-optimal work with parallelism, though it builds incrementally on existing reductions.
The paper tackles the problem of approximating partition functions in Gibbs distributions via sampling, presenting an algorithm that achieves near-optimal total work and efficient parallelism with logarithmic depth, leading to work-efficient parallel counting for models like the hardcore and Ising models in the uniqueness regime.
A canonical approach to approximating the partition function of a Gibbs distribution via sampling is simulated annealing. This method has led to efficient reductions from counting to sampling, including: $\bullet$ classic non-adaptive (parallel) algorithms with sub-optimal cost (Dyer-Frieze-Kannan '89; Bezáková-Å tefankoviÄ-Vazirani-Vigoda '08); $\bullet$ adaptive (sequential) algorithms with near-optimal cost (Å tefankoviÄ-Vempala-Vigoda '09; Huber '15; Kolmogorov '18; Harris-Kolmogorov '24). We present an algorithm that achieves both near-optimal total work and efficient parallelism, providing a reduction from counting to sampling with logarithmic depth and near-optimal work. As consequences, we obtain work-efficient parallel counting algorithms for several important models, including the hardcore and Ising models within the uniqueness regime.