Work-Efficient Parallel Derandomization I: Chernoff-like Concentrations via Pairwise Independence

by Mohsen Ghaffari, Christoph Grunau, and Vaclav Rozhon

Oded's comments

Loosely speaking, the issue at hand is derandomizing algorithms that are based on Chernoff-like concentration bounds, which typically require $k$-wise independence for large $k$. This is typically done using the method of conditional expectations, but the workload of this is exponential in $k$.

This work presents cases in which one can replace $n$ random choices that are $k$-wise independent by a sequence of $O(k^2)$ independent iterations that employ suitable $n$ pairwise independent choices. Specifically, each original 0-1 choice is replaced by a $O(k^2)$-step random walk (on a line), where the value is initialize at $1/2$ and each step randomizes the current value by an additive $\pm1/k$, until the value reaches either 0 or 1.

The point is that one can iteratively derandomize each iteration, individually, using the method of conditional expectations, and the cost is related to derandomizing pairwise independence rather than $k$-wise independence.

The strategy is not generic, but it is quite general since it applies to settings in which multiple choices are subject to multiple linear constraints such that totally independent choices satisfy the constraints.

See FOCS23 program.

Back to list of Oded's choices.