Theory of Computing
-------------------
Title     : Hitting Sets Give Two-Sided Derandomization of Small Space
Authors   : Kuan Cheng and William M. Hoza
Volume    : 18
Number    : 21
Pages     : 1-32
URL       : https://theoryofcomputing.org/articles/v018a021

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 $\mathbf{L} = \mathbf{RL}$ hold,
but $\mathbf{L} = \mathbf{BPL}$ as well. This answers a question
raised by Hoza and Zuckerman (SICOMP 2020).

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 $\pm \epsilon$ in
space $O(\log(n/\epsilon))$. Unconditionally, we give a deterministic
algorithm for this problem with space complexity $O(\log^2 n +
\log(1/\epsilon))$, 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 generator, 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.

-------------------

A conference version of this paper appeared in the
Proceedings of the 35th Computational Complexity Conference, 2020.