Two-source and affine extractors are two fundamental objects studied in the context of algorithmic derandomization. Explicit constructions of these two distinct objects seem to be related, at least on a superficial level. For instance, constructions of both objects for min-entropy rate above half have been known for quite some time [Chor, Goldreceich, SIAM J. Comp. 1988; Ben-Sasson et al. 2001], and much of the recent progress on both problems [Barak et al., 2006; Bourgain 2007] has relied on similar new sum-product theorems from additive combinatorics .
This paper establishes further connections between affine and two-source extractors by constructing two-source extractors for arbitrarily small min-entropy rate in a black-box manner from any affine extractor with sufficiently good parameters. Two such constructions are presented, and the first part of our analysis shows that they lead to two-source {\em dispersers} which are weak (but nontrivial) kinds of two-source extractors, also known as ``bipartite Ramsey graphs''.To strengthen this result and obtain two-source extractors we introduce the {\em approximate duality conjecture} (ADC) and initiate its study. The ADC leads to a rather general result that can be used to convert a natural class of two-source dispersers --- ``low-rank dispersers'' --- into two-source extractors. Suppose that a boolean two-input function $E\in F_2^{F_2^n\times F_2^n}$ is a two-source disperser for min-entropy rate $\rho$. Our main observation --- which uses the ADC --- is that if $E$ has rank $O(n)$ over $F_2$ when viewed as a $2^n\times 2^n$ matrix in the natural way, then $E$ is a two-source extractor for min-entropy rate $\rho+\delta$ (for any $\delta>0$) with exponentially small error!
The ADC is a natural conjecture in additive combinatorics so it deserves independent study, further motivation is provided by two recent applications of it to communication complexity [Ben-Sasson et al., FOCS 2012] and to locally decodable codes [Bhowmik et al., ECCC 2012]. Define the {\em duality measure} of a pair of sets $A,B\subset F_2^n$ to be
\[D(A,B)=\bigg|E_{a\in A, b\in B}\left[(-1)^{\sum_{i=1}^n a_i b_i}\right]\bigg|.\]
Then $D(A,B)=1$ if and only if $A$ is contained in an affine shift of the space dual to the span of $B$. The ADC says that every pair $(A,B)$ contains a pair of subsets $(A',B')$ that have duality measure exactly $1$, and the densities $|A'|/|A|$ and $|B'|/|B|$ increase with $D(A,B)$:
\[\min\{\frac{|A'|}{|A|}, \frac{|B'|}{|B|}\}\geq \exp\left(-c\sqrt{n \log(1/D(A,B))}\right)\]
for a positive universal constant $c$.
Our main technical result shows that a weak form of the ADC is implied by the {\em Polynomial Freiman-Ruzsa Conjecture} (PFR) in additive combinatorics (and that ADC also implies a weak but as-of-yet unknown version of the PFR), and that this version of the ADC is sufficient for obtaining the black-box construction of two-source extractors mentioned above.
Includes a cleaner statement of the "dream-version" of the ADC. Modified introduction and abstract.
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.
