Parallel Derandomization for Chernoff-like Concentrations

Event Type

Seminar/Symposium

Sponsor

The Department of Computer Science, University of Illinois Theory Group

Location

Siebel 3401

Virtual

Date

Apr 29, 2024   11:00 am  

Speaker

Mohsen Ghaffari (MIT)

Contact

Michael Forbes

E-Mail

miforbes@illinois.edu

Views

19

Originating Calendar

Siebel School Speakers Calendar

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 .