#
Deterministic Extractors

for Small-Space Sources

Jesse Kamp, Anup Rao, Salil Vadhan, and David Zuckerman

###
Abstract

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: For every constant delta>0,
we can extract .99*delta*n bits that are exponentially close to uniform (in
variation distance) from space s sources of min-entropy delta*n, where s=Omega(n).
In addition, assuming an efficient deterministic algorithm for finding large
primes, there is a constant eta >0 such that for any beta >n^{-eta}, we can
extract m=(delta-beta)*n bits that are exponentially close to uniform from space s sources with min-entropy delta*n, where s=Omega(beta^3 n).
Previously, nothing was known for delta<= 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 polylog(r), for small enough ell.

###
Versions

- In
*Proceedings of the 38th Annual ACM Symposium on Theory of
Computing (STOC `06), *pages 691-700, May 2006. [postscript][pdf][official
ACM page]
- To appear in
*Journal of Computer and System Sciences, *Special Issue to celebrate Richard Karp's Kyoto Prize, 2010. [pdf][JCSS page]

[
back to Salil Vadhan's research]