Simple and Fast Derandomization from Very Hard functions: Eliminating Randomness at Almost No Cost

by Lijie Chen and Roei Tell

The result outlined in the 2nd paragraph of the abstract essentially asserts that, under strong but reasonable intractability assumptions, it is possible to derandomized BPTime[T] by DTime[T'] such that $T'(n)=n^{1.01}\cdot T(n)$.

One insight that I gained from the paper is the following. Most work on de-randomization start by modelling a potential randomized decision procedure and the potential inputs to it by a non-uniform family of Boolean circuits. Consequently, derandomizind $BPtime(T)$ is reduced to constructing a pseudorandom generator that fools circuits of size $T$, which requires a seed of length at least $\log_2T$, which means that one cannot hope for a consequence that is better than $BPtime(T) \subseteq Dtime(T^2)$. In contrast, as observed and capitalized upon in this work, such a modelling blurs the fact that we need only deal with a linear amount of non-uniformity. Hence, $BPtime(T) \subseteq Dtime(T\cdot L)$, where $L(n)=n$, is potentially possible (and is essentially achieved, under some reasonable computational difficulty assumptions, in this work).

The original abstract

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 DTIME[2^n] that cannot be computed by randomized SVN circuits of size $2^{(1-\eps)n}$ for a small $\eps>0$.

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+\eps}$, under a hypothesis that is formally incomparable to the one of Doron et al., but is arguably more standard: We assume that there exist non-uniformly secure one-way functions, and that for $\delta=\delta(\eps)$ and $k=k_T(\eps)$ there exists a problem in DTIME[2^{kn}] that is hard for algorithms that run in time $2^{(k-\delta)n}$ and use $2^{(1-\delta)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+\eps} 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 in BPTime[n^k] there exists a deterministic algorithm A_L running in time $n^{k+\eps}$ such that for every distribution over n-bit strings that samplable in time $n^k$ it holds that $Pr_x[A_L(x)=L(x)]\geq1-n^{-omega(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).

Available from ECCC TR20-148.

Back to list of Oded's choices.