Simple Optimal Hitting Sets for Small-Success RL

We give a simple explicit hitting set generator for read-once branching programs of width $w$ and length $r$ with known variable order and acceptance probability at least $\varepsilon$. When $r = w$, our generator has seed length $O(\log^2 r + \log(1/\varepsilon))$. When $r = \text{polylog } w$, our generator has optimal seed length $O(\log w + \log(1/\varepsilon))$. For intermediate values of $r$, our generator's seed length smoothly interpolates between these two extremes. Our generator's seed length improves on recent work by Braverman, Cohen, and Garg (SICOMP 2020). In addition, our generator and its analysis are dramatically simpler than the work by Braverman et al. When $\varepsilon$ is small, our generator's seed length improves on all the classic generators for space-bounded computation (Nisan Combinatorica 1992; Impagliazzo, Nisan, and Wigderson STOC 1994; Nisan and Zuckerman JCSS 1996). However, all of these other works construct more general objects than we do. As a corollary of our construction, we show that every $\mathbf{RL}$ algorithm that uses $r$ random bits can be simulated by an $\mathbf{NL}$ algorithm that uses only $O(r/ \log^c n)$ nondeterministic bits, where c is an arbitrarily large constant. Finally, we show that any $\mathbf{RL}$ algorithm with small success probability $\varepsilon$ can be simulated deterministically in space $O(\log^{3/2} n + \log n \log \log(1/\varepsilon))$. This space bound improves on work by Saks and Zhou (JCSS 1999), who gave an algorithm for the more general "two-sided" problem that runs in space $O(\log^{3/2} n + \sqrt{\log n} \; \log(1/\varepsilon ))$.

In this paper, we present a set of binary strings $H$ with the following guarantee. Suppose $P$ is a property of binary strings such that a decent fraction of all binary strings have property $P$. Suppose also that there is some algorithm for determining whether a given string $x$ has property $P$, using a small amount of memory and reading $x$ just once from left to right. Then some string in $H$ has property $P$. Our set $H$ is smaller than any such set discovered previously.