Work-Efficient Parallel Derandomization I: Chernoff-like Concentrations via Pairwise Independence
METADATA ONLY
Loading...
Author / Producer
Date
2023
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
Abstract
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 inequalities. Our method increases the algorithm’s computational work and depth by only polylogarithmic factors. Before our work, the only known method to obtain parallel derandomization with such strong concentrations was by the results of [Motwani, Naor, and Naor FOCS’89; Berger and Rompel FOCS’89], which perform a binary search in a k-wise independent space for k=poly(logn). However, that method blows up the computational work by a high poly (n) factor and does not yield work-efficient parallel algorithms. Their method was an extension of the approach of [Luby FOCS’88], which gave a work-efficient derandomization but was limited to algorithms analyzed with only pairwise independence. Pushing the method from pairwise to the higher k-wise analysis resulted in the poly(n) factor computational work blow-up. Our work can be viewed as an alternative extension from the pairwise case, which yields the desired strong concentrations while retaining work efficiency up to logarithmic factors. Our approach works by casting the problem of determining the random variables as an iterative process with poly (logn) iterations, where different iterations have independent randomness. This is done so that for the desired concentrations, we need only pairwise independence inside each iteration. In particular, we model each binary random variable as a result of a gradual random walk, and our method shows that the desired Chernoff-like concentrations about the endpoints of these walks can be boiled down to some pairwise analysis on the steps of these random walks in each iteration (while having independence across iterations). Hence, we can fix the randomness of each iteration efficiently before proceeding to the next.
Permanent link
Publication status
published
External links
Editor
Book title
2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)
Journal / series
Volume
Pages / Article No.
1551 - 1562
Publisher
IEEE
Event
64th IEEE Symposium on the Foundations of Computer Science (FOCS 2023)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Parallel derandomization; Chernoff bound; Concentration bounds; Work-efficiency
Organisational unit
09587 - Ghaffari, Mohsen (ehemalig) / Ghaffari, Mohsen (former)
03457 - Welzl, Emo (emeritus) / Welzl, Emo (emeritus)