2 papers
cs.DS2023
Work-Efficient Parallel Derandomization II: Optimal Concentrations via Bootstrapping
Mohsen Ghaffari, Christoph Grunau
We present an efficient parallel derandomization method for randomized algorithms that rely on concentrations such as the Chernoff bound. This settles a classic problem in parallel…
cs.DS2023
Work-Efficient Parallel Derandomization I: Chernoff-like Concentrations via Pairwise Independence
Mohsen Ghaffari, Christoph Grunau, Václav Rozhoň
We present a novel technique for work-efficient parallel derandomization, for algorithms that rely on the concentration of measure bounds such as Chernoff, Hoeffding, and Bernstein…