Parallel Derandomization for Chernoff-like Concentrations

Speaker: Mohsen Ghaffari , CSAIL MIT

Date: Tuesday, May 07, 2024

Time: 4:15 PM to 5:15 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: 32-G882

Event Type:

Room Description: Refreshments at 4:00pm

Host: Sam Hopkins, CSAIL MIT

Contact: Joanne Talbot Hanley, 617-253-6054, joanne@csail.mit.edu

Relevant URL:

Speaker URL: None

Speaker Photo:
None

Reminders to: seminars@csail.mit.edu, theory-seminars@csail.mit.edu

Reminder Subject: TALK: TOC Seminar: Parallel Derandomization for Chernoff-like Concentrations by Mohsen Ghaffari, Tuesday, May 7 at 4:15pm in 32-G882, Refreshments at 4:00pm

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 disadvanage: 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 work with Christoph Grunau and Vaclav Rozhon, which can be accessed via https://arxiv.org/abs/2311.13764 and https://arxiv.org/abs/2311.13771.

Research Areas:

Impact Areas:

See other events that are part of the Theory of Computation (ToC) Seminar 2024.

Created by Joanne Talbot Hanley Email at Tuesday, April 16, 2024 at 1:16 PM.