Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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