Ziv Bar-Yossef, Oded Goldreich, Avi Wigderson

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

William Hoza, David Zuckerman

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