  We present an efficient parallel derandomization method for randomized
algorithms that rely on concentrations such as the Chernoff bound. This settles
a classic problem in parallel derandomization, which dates back to the 1980s.
Consider the \textit{set balancing} problem where $m$ sets of size at most $s$
are given in a ground set of size $n$, and we should partition the ground set
into two parts such that each set is split evenly up to a small additive
(discrepancy) bound. A random partition achieves a discrepancy of $O(\sqrt{s
\log m})$ in each set, by Chernoff bound. We give a deterministic parallel
algorithm that matches this bound, using near-linear work and polylogarithmic
depth. The previous results were weaker in discrepancy and/or work bounds:
Motwani, Naor, and Naor [FOCS'89] and Berger and Rompel [FOCS'89] achieve
discrepancy $s^{\varepsilon} \cdot O(\sqrt{s \log m})$ with work
$\tilde{O}(m+n+\sum_{i=1}^{m} |S_i|) \cdot m^{\Theta(1/\varepsilon)}$ and
polylogarithmic depth; the discrepancy was optimized to $O(\sqrt{s \log m})$ in
later work, e.g. by Harris [Algorithmica'19], but the work bound remained high
at $\tilde{O}(m^4n^3)$. Ghaffari, Grunau, and Rozhon [FOCS'23] achieve
discrepancy $s/poly(\log(nm)) + O(\sqrt{s \log m})$ with near-linear work and
polylogarithmic-depth. Notice that this discrepancy is barely sublinear with
respect to the trivial bound of $s$. Our method relies on a novel bootstrapping
idea that uses crude partitioning algorithms as a subroutine. In particular, we
solve the problem recursively, by using the crude partition in each iteration
to split the variables into many smaller parts, and then we find a constraint
for the variables in each part such that we reduce the overall number of
variables in the problem. The scheme relies on an interesting application of
the multiplicative weights update method to control the variance losses in each
iteration.
