Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > L VS. RL:
Reports tagged with L vs. RL:
TR18-063 | 5th April 2018
William Hoza, David Zuckerman

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

Revisions: 1

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 ... more >>>

TR20-016 | 17th February 2020
Kuan Cheng, William Hoza

#### Hitting Sets Give Two-Sided Derandomization of Small Space

Revisions: 1

A hitting set is a "one-sided" variant of a pseudorandom generator (PRG), naturally suited to derandomizing algorithms that have one-sided error. We study the problem of using a given hitting set to derandomize algorithms that have two-sided error, focusing on space-bounded algorithms. For our first result, we show that if ... more >>>

ISSN 1433-8092 | Imprint