From the 1 of 4 linked papers with an AI index.
4 papers
Online Random Sampling with Real Probabilities
Thomas L. Draper, David G. Harris, Feras A. Saad
The paper presents an online algorithm that samples from a sequence of discrete distributions using only fair coin flips, achieving near‑optimal entropy usage while using only loga…
Near-Optimal Parallel Approximate Counting via Sampling
David G. Harris, Vladimir Kolmogorov, Hongyang Liu +2
The computational equivalence between approximate counting and sampling is well established for polynomial-time algorithms. The most efficient general reduction from counting to sa…
Improved parallel derandomization via finite automata with applications
Jeff Giliberti, David G. Harris
A central approach to algorithmic derandomization is to construct probability distributions with small support that "fool" randomized algorithms, often enabling efficient parallel…
Scalable Algorithms for Approximate DNF Model Counting
Paul Burkhardt, David G. Harris, Kevin T Schmitt
Model counting of Disjunctive Normal Form (DNF) formulas is a critical problem in applications such as probabilistic inference and network reliability. For example, it is often use…