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

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.