## 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.