We propose a new model of weak random sources which we call sumset sources. A sumset source $\mathbf{X}$ is the sum of $C$ independent sources $\mathbf{X}_1,\ldots,\mathbf{X}_C$, where each $\mathbf{X}_i$ is an $n$-bit source with min-entropy $k$. We show that extractors for this class of sources can be used to give extractors for most classes of weak sources that have been studied previously, including independent sources, affine sources (which generalizes oblivious bit-fixing sources), small space sources, total entropy independent sources, and interleaved sources. This provides a unified approach for randomness extraction.
A known extractor for this class of sources, prior to our work, is the Paley graph function introduced by Chor and Goldreich, which works for the sum of $2$ independent sources, where one has min-entropy at least $0.51n$ and the other has min-entropy $O(\log n)$. To the best of our knowledge, the only other known construction is from the work of Kamp et al., which can extract from the sum of exponentially many independent sources.
Our main result is an explicit extractor for the sum of $C$ independent sources for some large enough constant $C$, where each source has min-entropy polylog(n). We then use this extractor to obtain the following results for other well studied classes of sources.
(1) $\text{Small-space sources}$: This is the class of sources generated by a small width branching program. Previously the best known extractor by Kamp et al. requires min-entropy $k \ge n^{1-\delta}$ even for space $1$, where $\delta>0$ is a small constant. We improve the min-entropy to $k \ge 2^{\log^{0.51}(n)}s^{1.1}$ for space $s$, which is $n^{o(1)}$ for $s=n^{o(1)}$.
(2) $\text{Affine Sources}$: This constitutes the class of sources that are uniform over some affine subspace in $\mathbb{F}_2^n$. A direct corollary of our sumset extractor gives an explicit affine extractor for entropy $polylog(n)$, matching the recent work of Li.
(3) $\text{Interleaved Sources}$: We obtain new results on extracting from an unknown interleaving of the bits of $C$ independent sources. This model was studied by Raz and Yehudayoff in the context of proving circuit lower bounds, and subsequently by Chattopadhyay and Zuckerman. Previous results require at least one source to have min-entropy $(1-\delta)n$ for a small constant $\delta>0$. We give explicit extractors for the interleaving of a constant number of sources each with polylogarithmic min-entropy.
We also give improved extractors for total entropy independent sources, introduced by Kamp et al., and a simple extractor for somewhere-$2$ sources, which generalizes the model of $2$-independent sources to a large collection of independent sources with the guarantee that at least two sources contain polylogarithmic min-entropy.
