Abstract:
Randomized algorithms frequently use concentration results such as Chernoff and Hoeffding bounds. A longstanding challenge in parallel computing is to devise an efficient method to derandomize parallel algorithms that rely on such concentrations. Classic works of Motwani, Naor, and Naor [FOCS'89] and Berger and Rompel [FOCS'89] provide an elegant parallel derandomization method for these, via a binary search in a k-wise independent space, but with one major disadvantage: it blows up the computational work by a (large) polynomial. That is, the resulting deterministic parallel algorithm is far from work-efficiency and needs polynomial processors even to match the speed of single-processor computation. This talk overviews a duo of recent papers that provide the first nearly work-efficient parallel derandomization method for Chernoff-like concentrations.
Based on joint works with Christoph Grunau and Vaclav Rozhon. FOCS '23, arxiv.org/abs/2311.13764 . STOC '24, arxiv.org/abs/2311.13771 .
