# Deterministic extractors for small-space sources

### Citation:

Kamp, Jesse, Anup Rao, Salil Vadhan, and David Zuckerman. “Deterministic extractors for small-space sources.” Journal of Computer and System Sciences 77, no. 1 (2011): 191-220.
 JCSS2011.pdf 432 KB STOC-05-2006.pdf 258 KB

### Abstract:

Version History: Special issue to celebrate Richard Karp's Kyoto Prize. Extended abstract in STOC '06.

We give polynomial-time, deterministic randomness extractors for sources generated in small space, where we model space $$s$$ sources on$$\{0,1\}^n$$ as sources generated by width $$2^s$$ branching programs. Specifically, there is a constant $$η > 0$$ such that for any $$ζ > n^{−η}$$, our algorithm extracts $$m = (δ − ζ)n$$ bits that are exponentially close to uniform (in variation distance) from space $$s$$ sources with min-entropy $$δn$$, where $$s = Ω(ζ^ 3n)$$. Previously, nothing was known for $$δ \ll 1/2,$$, even for space $$0$$. Our results are obtained by a reduction to the class of total-entropy independent sources. This model generalizes both the well-studied models of independent sources and symbol-fixing sources. These sources consist of a set of $$r$$ independent smaller sources over $$\{0, 1\}^\ell$$, where the total min-entropy over all the smaller sources is $$k$$. We give deterministic extractors for such sources when $$k$$ is as small as $$\mathrm{polylog}(r)$$, for small enough $$\ell$$.

Publisher's Version

Last updated on 07/17/2020