We consider the problem of extracting randomness from \textit{sumset sources}, a general class of weak sources introduced by Chattopadhyay and Li (STOC, 2016). An (n,k,C)-sumset source \mathbf{X} is a distribution on \{0,1\}^n of the form \mathbf{X}_1 + \mathbf{X}_2 + \ldots + \mathbf{X}_C, where \mathbf{X}_i's are independent sources on n bits with min-entropy at least k. Prior extractors either required the number of sources C to be a large constant or the min-entropy k to be at least 0.51 n.

As our main result, we construct an explicit extractor for sumset sources in the setting of C=2 for min-entropy \mathrm{poly}(\log n) and polynomially small error. We can further improve the min-entropy requirement to (\log n) \cdot (\log \log n)^{1 + o(1)} at the expense of worse error parameter of our extractor. We find applications of our sumset extractor for extracting randomness from other well-studied models of weak sources such as affine sources, small-space sources, and interleaved sources.

Interestingly, it is unknown if a random function is an extractor for sumset sources. We use techniques from additive combinatorics to show that it is a disperser, and further prove that an affine extractor works for an interesting subclass of sumset sources which informally corresponds to the ``low doubling" case
(i.e., the support of \mathbf{X_1} + \mathbf{X_2} is not much larger than 2^k).

fixed some typos

We consider the problem of extracting randomness from \textit{sumset sources}, a general class of weak sources introduced by Chattopadhyay and Li (STOC, 2016). An (n,k,C)-sumset source \mathbf{X} is a distribution on \{0,1\}^n of the form \mathbf{X}_1 + \mathbf{X}_2 + \ldots + \mathbf{X}_C, where \mathbf{X}_i's are independent sources on n bits with min-entropy at least k. Prior extractors either required the number of sources C to be a large constant or the min-entropy k to be at least 0.51 n.

As our main result, we construct an explicit extractor for sumset sources in the setting of C=2 for min-entropy \mathrm{poly}(\log n) and polynomially small error. We can further improve the min-entropy requirement to (\log n) \cdot (\log \log n)^{1 + o(1)} at the expense of worse error parameter of our extractor. We find applications of our sumset extractor for extracting randomness from other well-studied models of weak sources such as affine sources, small-space sources, and interleaved sources.