## Nearly Optimal Derandomization under Assumptions

by Dean Doron, Dana Moshkovitz, Justin Oh, and David Zuckerman

#### Oded's comments

The fact that the known derandomization of BPP comes
at a cost is often understated. Saying that *randomization
is useless as far as decision problems are concerned*,
let alone making even less qualified statements,
makes things even worse.
In contrast, it is clear that any canonical derandomizer
(see Sec 8.3 in my complexity book)
must use a seed that is longer than logarithmic (to base 2)
in the desired output length, and so the running time of
the deterministic procedure obtained by trying all seeds is at
least quadratic in the running time of the randomized algorithm.
A `back of the envelop' calculation shows that when starting
with the assumption that computing some predicate in E
requires $m$-bit circuits of size $2^{\eps m}$,
the NW-generator producing $\ell$ bits uses
a seed of length at least $(8/\eps^2)\log_2\ell$.
Can we do better?
More generally, can we derandomize $BPTime(t)$
by $Dtime(t')$ for $t'$ smaller than $t^9$?

This paper answers the second question
(but not the first... (as far as I could tell)),
using a stronger assumption than the one used to establish BPP=P,
but similar to the one that has been used for establishing
a few related derandomization results (e.g., AM=NP).
Specificxally, the assumption is that,
computing some predicate in E requires $m$-bit non-deterministic circuits
of size $2^{(1-\eps) m}$ for some sufficiently small constant $\eps$.

**Correction (May 2020):**
The required hardness is for a non-uniform analogue of MATIME[2^{.99n}]
rather than for a non-uniform analogue of NTIME[2^{.99n}]
as they initially stated and cited.

#### The original abstract

Existing proofs that deduce BPP=P from circuit lower bounds convert
randomized algorithms to deterministic algorithms with a large polynomial
slowdown. We convert randomized algorithms to deterministic algorithms with
nearly minimal slowdown. Specifically, assuming exponential lower bounds
against non-deterministic circuits we convert randomized algorithms that err
rarely to deterministic algorithms with a similar run-time, and general
randomized algorithms to deterministic algorithms whose run-time is slower by
only a nearly linear factor.
Our results follow from a new connection between pseudo-entropy generators
and locally list recoverable codes.

See ECCC TR19-099.

Back to
list of Oded's choices.