Paper Info
Title
Simple Optimal Hitting Sets for Small-Success RL
Abstract
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 r + log(1/ε)). When r = polylog w, our generator has optimal seed length O(log w + log(1/ε)). 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/ε)). 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/ε)).
Year
DOI
Venue
2018
10.1109/FOCS.2018.00015
2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)
Keywords
Field
DocType
pseudorandom,derandomization,hitting sets,space complexity,branching programs
Log-log plot,Discrete mathematics,Binary logarithm,Combinatorics,Nondeterministic algorithm,Corollary,Arbitrarily large,Mathematics,Computation,Branching (version control)
Conference
Volume
Issue
ISSN
25
4
1523-8288
ISBN
Citations 
PageRank 
978-1-5386-4231-3
0
0.34
References 
Authors
11
2
Name
Order
Citations
PageRank
William M. Hoza113.74
David Zucherman22588266.65