Extractors for sum of two sources

We consider the problem of extracting randomness from sumset sources, a general class of weak sources introduced by Chattopadhyay and Li (STOC, 2016). An (n, k, C)-sumset source X is a distribution on 0, 1 n of the form X1 +X2 +. . .+XC, where Xi'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.51n. As our main result, we construct an explicit extractor for sumset sources in the setting of C = 2 for min-entropy poly(log n) and polynomially small error. We can further improve the min-entropy requirement to (log n) • (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 X1 + X2 is not much larger than 2 k ).