Deterministic extractors for small-space sources

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 $\eta >0$ such that for any $\zeta >n^{?\eta }$, our algorithm extracts $m=(\delta ?\zeta )n$ bits that are exponentially close to uniform (in variation distance) from space s sources with min-entropy δn, where $s=\Omega ({\zeta }^{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\}}^{?}$, 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 $\mathsf{polylog}(r)$, for small enough ?.