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. When r = w, our generator has seed length O(log^2 w + log(1/eps)). When r = polylog w, our generator has optimal seed length O(log w + log(1/eps)). 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 (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 eps is small. As a corollary of our construction, we show that every RL algorithm that uses r random bits can be simulated by an NL algorithm that uses only O(r/log^c n) nondeterministic bits, where c is an arbitrarily large constant. Finally, we show that any RL algorithm with small success probability eps can be simulated deterministically in space O(log^{3/2} n + log n log log(1/eps)). 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/eps)).

This is joint work with William Hoza.