Hitting Sets Give Two-Sided Derandomization of Small Space

by Kuan Cheng and William Hoza

Oded's comments

I missed this ECCC posting (as well as the CCC20 publication) in real time, but today thinking in the direction of the proof presented in its Appendix A (and wondering about an analogous result for log-sapce), I searched the web and found this paper....

Indeed, Appendix A presents another proof for the fact that a hitting-set generator (for poly-sized circuits) implies BPP=P (rather than only $RP=P$). The proof is indeed simpler than the one in my paper with Salil and Avi, which in turn simplified my proof with Avi, but unlike these proofs the new proof does not scale well to the case that the hitting set generator (HSG) runs in time $T(s)$ rather than $\poly(s)$, where $s$ is the circuit size. Specifically, in this case the current proof places $\BPtime(t)$ essentially in $\Dtime(T(T(t)))$, rather than $\Dtime(\poly(T(t))$. (See my notes.) This is the case, since the current proof uses the HSG both for a circuit directly derived from the algorithm (which has size related to $t$) and for a circuit that compute the former HSG (which has size related to $T(t)$), whereas the previous aforementioned proofs avoid the second use.

The original abstract

A hitting set is a "one-sided" variant of a pseudorandom generator (PRG), naturally suited to derandomizing algorithms that have one-sided error. We study the problem of using a given hitting set to derandomize algorithms that have two-sided error, focusing on space-bounded algorithms. For our first result, we show that if there is a log-space hitting set for polynomial-width read-once branching programs (ROBPs), then not only does L=RL, but L=BPL as well. This answers a question raised by Hoza and Zuckerman (FOCS 2018).

Next, we consider constant-width ROBPs. We show that if there are log-space hitting sets for constant-width ROBPs, then given black-box access to a constant-width ROBP f, it is possible to deterministically estimate E[f] to within $\eps$ in space $O(log(n/\eps))$. Unconditionally, we give a deterministic algorithm for this problem with space complexity $O(log^2n+log(1/\eps))$, slightly improving over previous work.

Finally, we investigate the limits of this line of work. Perhaps the strongest reduction along these lines one could hope for would say that for every explicit hitting set, there is an explicit PRG with similar parameters. In the setting of constant-width ROBPs over a large alphabet, we prove that establishing such a strong reduction is at least as difficult as constructing a good PRG outright. Quantitatively, we prove that if the strong reduction holds, then for every constant $\alpha>0$, there is an explicit PRG for constant-width ROBPs with seed length $O(log^{1+\alpha}n)$. Along the way, unconditionally, we construct an improved hitting set for ROBPs over a large alphabet.

Available from ECCC TR20-016.

Back to list of Oded's choices.