Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR18-063 | 9th April 2018 17:07

Simple Optimal Hitting Sets for Small-Success $\mathbf{RL}$

RSS-Feed




Revision #1
Authors: William Hoza, David Zuckerman
Accepted on: 9th April 2018 17:07
Downloads: 1489
Keywords: 


Abstract:

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))$.



Changes to previous version:

Fixed typos


Paper:

TR18-063 | 5th April 2018 22:50

Simple Optimal Hitting Sets for Small-Success $\mathbf{RL}$





TR18-063
Authors: William Hoza, David Zuckerman
Publication: 8th April 2018 13:19
Downloads: 1429
Keywords: 


Abstract:

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))$.



ISSN 1433-8092 | Imprint