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 \minrate > n^{-\eta}, we can extract
m=(\delta-\minrate)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
\leq 1/2, even for space 0.
Our results are obtained by a reduction to a new class of sources
that we call "independent-symbol" sources, which generalize both
the well-studied models of independent sources and symbol-fixing
sources. These sources consist of a string of n independent
symbols over a d symbol alphabet with min-entropy k. We give
deterministic extractors for such sources when k is as small as
\polylog(n), for small enough~d.
