Two-source and affine extractors and dispersers are fundamental objects studied in the context of derandomization. This paper shows how to construct two-source extractors and dispersers for arbitrarily small min-entropy rate in a black-box manner from affine extractors with sufficiently good parameters. Our analysis relies on the study of approximate duality, a concept related to the polynomial Freiman-Ruzsa conjecture (PFR) from additive combinatorics.

Two black-box constructions of two-source extractors from affine ones are presented. Both constructions work for min-entropy rate $\rho<1/2$. One of them can potentially reach arbitrarily mall min-entropy rate provided the affine extractor used to construct it outputs, on affine sources of min-entropy rate 1/2, a relatively large number of output bits and has sufficiently small error. This shows that for purposes of constructing better two-source extractors, minimizing the error of
affine extractors is more important than decreasing their min-entropy rate.

Our results are obtained by first showing that each of our constructions yields a two-source disperser for a certain min-entropy rate $\rho<1/2$ and then using a general extractor-to-disperser reduction that applies to a large family of constructions. This reduction says that any two-source disperser for min-entropy rate $\rho$ coming from this family is also a two-source extractor for min-entropy rate $\rho+\epsilon$ for arbitrarily small $\epsilon>0$.

The extractor-to-disperser reduction arises from studying approximate duality, a notion related to additive combinatorics. The duality measure of two sets $A,B\subseteq \{0,1\}^n$ aims to quantify how "close" these sets are to being dual and is defined as $\mu^\perp(A,B)=\left|E_{a\in A, b\in B}\left[(-1)^{\sum_{i=1}^n a_i b_i}\right]\right|.$ Notice that $\mu^\perp(A,B)=1$ implies that $A$ is contained in an affine shift of $B^\perp$ --- the space dual to the $\{0,1\}$-span of $B$. We study what can be said of $A,B$ when their duality measure is large but strictly smaller than $1$ and show that $A,B$ contain subsets $A',B'$ of nontrivial size for which $\mu^\perp(A',B')=1$ and consequently $A'$ is contained in an affine shift of $(B')^\perp$. Surprisingly, the PFR implies that such $A',B'$ exist even if the duality measure is exponentially small in $n$, and this implication leads to two-source extractors with exponentially small error.