We give a simple explicit hitting set generator for read-once branching programs of width $w$ and length $r$ with known variable order. Our generator has seed length $O\left(\frac{\log(wr) \log r}{\max\{1, \log \log w - \log \log r\}} + \log(1/\varepsilon)\right)$. This seed length improves on recent work by Braverman, Cohen, and Garg (STOC '18). In addition, our generator and its analysis are dramatically simpler than the work by Braverman et al. Our generator's seed length improves on all the classic generators for space-bounded computation (Nisan Combinatorica '92; Impagliazzo, Nisan, and Wigderson STOC '94; Nisan and Zuckerman JCSS '96) when $\varepsilon$ is small.

When $r \leq \text{polylog } w$, our generator has optimal seed length $O(\log w + \log(1/\varepsilon))$. As a corollary, 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 improves on work by Saks and Zhou (JCSS '99), who gave an algorithm that runs in space $O(\log^{3/2} n + \sqrt{\log n} \log(1/\varepsilon))$.

Fixed typos

We give a simple explicit hitting set generator for read-once branching programs of width $w$ and length $r$ with known variable order. Our generator has seed length $O\left(\frac{\log(wr) \log r}{\max\{1, \log \log w - \log \log r\}} + \log(1/\varepsilon)\right)$. This seed length improves on recent work by Braverman, Cohen, and Garg (STOC '18). In addition, our generator and its analysis are dramatically simpler than the work by Braverman et al. Our generator's seed length improves on all the classic generators for space-bounded computation (Nisan Combinatorica '92; Impagliazzo, Nisan, and Wigderson STOC '94; Nisan and Zuckerman JCSS '96) when $\varepsilon$ is small.

When $r \leq \text{polylog } w$, our generator has optimal seed length $O(\log w + \log(1/\varepsilon))$. As a corollary, 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 improves on work by Saks and Zhou (JCSS '99), who gave an algorithm that runs in space $O(\log^{3/2} n + \sqrt{\log n} \log(1/\varepsilon))$.