Simple and fast derandomization from very hard functions: eliminating randomness at almost no cost

Extending the classical "hardness-to-randomness" line-of-works, Doron et al. (FOCS 2020) recently proved that derandomization with near-quadratic time overhead is possible, under the assumption that there exists a function in DT IME [2 n ] that cannot be computed by randomized SVN circuits of size 2 (1-)•n for a small .

In this work we extend their inquiry and answer several open questions that arose from their work. Our main result is that derandomization with almost no time overhead is possible, under a plausible hypothesis. Specifically, we show that probabilistic algorithms that run in time T(n) can be deterministically simulated in time n • T(n) 1+ , under a hypothesis that is formally incomparable to the one of Doron et al., but is arguably more standard: We assume that there exist nonuniformly secure one-way functions, and that for δ = δ( ) and k = k T ( ) there exists a problem in DT IME [2 k•n ] that is hard for algorithms that run in time 2 (k-δ)•n and use 2 (1-δ)•n bits of advice. We also show that the latter hypothesis (or, more accurately, a relaxation of it that we use) is in fact necessary to obtain the derandomization conclusion if one relies on a PRG construction (as is indeed our approach).

For sub-exponential time functions T(n) = 2 n o(1) we further improve the derandomization time to n 1+ • T(n), under a mildly stronger hypothesis. We also show that the multiplicative time overhead of n is essentially optimal, conditioned on a counting version of the non-deterministic strong exponential-time hypothesis (i.e., on #NSETH). Nevertheless, we show that in the average-case setting a faster derandomization is possible: Under hypotheses similar to the ones in our main result, we show that for every L ∈ BP T IME [n k ] there exists a deterministic algorithm A L running in time n • n k such that for every distribution D over 0, 1 n samplable in time n k it holds that Pr x∼D [A L (x) = L(x)] ≥ 1n -ω(1) .

Lastly, we present an alternative proof for the result of Doron et al. using a proof paradigm that is both considerably simpler and more general; in fact, we show how to simplify the analysis of any construction that "extracts randomness from a pseudoentropic string". We use this simpler proof to extend their result, deducing a mildly slower derandomization (i.e., with cubic or quadratic overhead) from weaker hardness assumptions (i.e., for SVN circuits that do not use randomness).