Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > SPACE BOUNDED RANDOMIZED COMPUTATION:
Reports tagged with Space Bounded Randomized Computation:
TR98-072 | 14th December 1998
Ziv Bar-Yossef, Oded Goldreich, Avi Wigderson

#### Deterministic Amplification of Space Bounded Probabilistic Algorithms.

This paper initiates the study of deterministic amplification of space
bounded probabilistic algorithms. The straightforward implementations of
known amplification methods cannot be used for such algorithms, since they
consume too much space. We present a new implementation of the
Ajtai-Koml\'{o}s-Szemer\'{e}di method, that enables to amplify an $S$ ... more >>>

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

ISSN 1433-8092 | Imprint