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.