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

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