Deterministic Extractors
for Small-Space Sources

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


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.


 [ back to Salil Vadhan's research]