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
- Join online
- Date
- Apr 29, 2024 11:00 am
- Speaker
- Mohsen Ghaffari (MIT)
- Contact
- Michael Forbes
- miforbes@illinois.edu
- Views
- 133
- 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 .