4 papers · 1 filter
Online Random Sampling with Real Probabilities
Thomas L. Draper, David G. Harris, Feras A. Saad
We develop an efficient online algorithm to sample a sequence of discrete random variables using an entropy source of i.i.d. fair coin flips, in a standard model of real computatio…
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…
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…
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…