ECCC-Report TR18-063https://eccc.weizmann.ac.il/report/2018/063Comments and Revisions published for TR18-063en-usMon, 09 Apr 2018 17:07:06 +0300
Revision 1
| Simple Optimal Hitting Sets for Small-Success $\mathbf{RL}$ |
William Hoza,
David Zuckerman
https://eccc.weizmann.ac.il/report/2018/063#revision1We 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))$.Mon, 09 Apr 2018 17:07:06 +0300https://eccc.weizmann.ac.il/report/2018/063#revision1
Paper TR18-063
| Simple Optimal Hitting Sets for Small-Success $\mathbf{RL}$ |
William Hoza,
David Zuckerman
https://eccc.weizmann.ac.il/report/2018/063We 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))$.Sun, 08 Apr 2018 13:19:03 +0300https://eccc.weizmann.ac.il/report/2018/063