We explicitly construct an extractor for two independent sources on $n$ bits, each with min-entropy at least $\log^C n$ for a large enough constant~$C$. Our extractor outputs one bit and has error $n^{-\Omega(1)}$. The best previous extractor, by Bourgain, required each source to have min-entropy $.499n$.

A key ingredient in our construction is an explicit construction of a monotone, almost-balanced Boolean function on $n$ bits that is resilient to coalitions of size $n^{1-\delta}$, for any $\delta>0$. In fact, our construction is stronger in that it gives an explicit extractor for a generalization of non-oblivious bit-fixing sources on $n$ bits, where some unknown $n-q$ bits are chosen almost $\polylog(n)$-wise independently, and the remaining $q=n^{1-\delta}$ bits are chosen by an adversary as an arbitrary function of the $n-q$ bits. The best previous construction, by Viola, achieved $q=n^{1/2 - \delta}$.

Our explicit two-source extractor directly implies an explicit construction of a $2^{(\log \log N)^{O(1)}}$-Ramsey graph over $N$ vertices, improving bounds obtained by Barak et al.\ and matching an independent work by Cohen.

fixed some more typos and minor errors.

We explicitly construct an extractor for two independent sources on $n$ bits, each with min-entropy at least $\log^C n$ for a large enough constant~$C$. Our extractor outputs one bit and has error $n^{-\Omega(1)}$. The best previous extractor, by Bourgain, required each source to have min-entropy $.499n$.

A key ingredient in our construction is an explicit construction of a monotone, almost-balanced boolean function on $n$ bits that is resilient to coalitions of size $n^{1-\delta}$, for any $\delta>0$. In fact, our construction is stronger in that it gives an explicit extractor for a generalization of non-oblivious bit-fixing sources on $n$ bits, where some unknown $n-q$ bits are chosen almost $\polylog(n)$-wise independently, and the remaining $q=n^{1-\delta}$ bits are chosen by an adversary as an arbitrary function of the $n-q$ bits. The best previous construction, by Viola, achieved $q=n^{1/2 - \delta}$.

Our explicit two-source extractor directly implies an explicit construction of a $2^{(\log \log N)^{O(1)}}$-Ramsey graph over $N$ vertices, improving bounds obtained by Barak et al.\ and matching an independent work by Cohen.

Improvements to presentation and explanations in Section 5 of previous version. Other minor changes.

We explicitly construct an extractor for two independent sources on $n$ bits, each with min-entropy at least $\log^C n$ for a large enough constant~$C$. Our extractor outputs one bit and has error $n^{-\Omega(1)}$. The best previous extractor, by Bourgain, required each source to have min-entropy $.499n$.

A key ingredient in our construction is an explicit construction of a monotone, almost-balanced boolean function on $n$ bits that is resilient to coalitions of size $n^{1-\delta}$, for any $\delta>0$. In fact, our construction is stronger in that it gives an explicit extractor for a generalization of non-oblivious bit-fixing sources on $n$ bits, where some unknown $n-q$ bits are chosen almost $\polylog(n)$-wise independently, and the remaining $q=n^{1-\delta}$ bits are chosen by an adversary as an arbitrary function of the $n-q$ bits. The best previous construction, by Viola, achieved $q=n^{1/2 - \delta}$.

Our explicit two-source extractor directly implies an explicit construction of a $2^{(\log \log N)^{O(1)}}$-Ramsey graph over $N$ vertices, improving bounds obtained by Barak et al.\ and matching an independent work by Cohen.

Major revision of presentation and structure of the paper--includes more detailed explanations.

We explicitly construct an extractor for two independent sources on $n$ bits, each with min-entropy at least $\log^C n$ for a large enough constant~$C$. Our extractor outputs one bit and has error $n^{-\Omega(1)}$. The best previous extractor, by Bourgain, required each source to have min-entropy $.499n$.

A key ingredient in our construction is an explicit construction of a monotone, almost-balanced boolean function on $n$ bits that is resilient to coalitions of size $n^{1-\delta}$, for any $\delta>0$. In fact, our construction is stronger in that it gives an explicit extractor for a generalization of non-oblivious bit-fixing sources on $n$ bits, where some unknown $n-q$ bits are chosen almost $\polylog(n)$-wise independently, and the remaining $q=n^{1-\delta}$ bits are chosen by an adversary as an arbitrary function of the $n-q$ bits. The best previous construction, by Viola, achieved $q=n^{1/2 - \delta}$.

Our explicit two-source extractor directly implies an explicit construction of a $2^{(\log \log N)^{O(1)}}$-Ramsey graph over $N$ vertices,
improving bounds obtained by Barak et al. and matching independent work by Cohen.

(1) a more detailed sketch of our 2-source extractor in the introduction (Section 1.2). (2) added Theorem 2, which gives 2-source extractors for arbitrary error, at expense of more running time. (Proof sketch of this is given in Section 7). (3) various other minor edits.

We explicitly construct an extractor for two independent sources on $n$ bits, each with min-entropy at least $\log^C n$ for a large enough constant~$C$.
Our extractor outputs one bit and has error $n^{-\Omega(1)}$.
The best previous extractor, by Bourgain, required each source to have min-entropy $.499n$.

A key ingredient in our construction is an explicit construction of a monotone, almost-balanced boolean function on $n$ bits that is resilient to coalitions of size $n^{1-\delta}$, for any $\delta>0$.
In fact, our construction is stronger in that it gives an explicit extractor for a generalization of non-oblivious bit-fixing sources on $n$ bits, where some unknown
$n-q$ bits are chosen almost $\polylog(n)$-wise independently, and the remaining $q=n^{1-\delta}$ bits are chosen by an adversary as an arbitrary function of the $n-q$ bits.
The best previous construction, by Viola, achieved $q=n^{1/2 - \delta}$.

Our explicit two-source extractor directly implies an explicit construction of a $2^{(\log \log N)^{O(1)}}$-Ramsey graph over $N$ vertices,
improving bounds obtained by Barak et al.\ and matching independent work by Cohen.

Expanded introduction and added more explanation.

We explicitly construct an extractor for two independent sources on $n$ bits, each with min-entropy at least $\log^C n$ for a large enough constant $C$. Our extractor outputs one bit and has error $n^{-\Omega(1)}$. The best previous extractor, by Bourgain [B2], required each source to have min-entropy $.499n$.

A key ingredient in our construction is an explicit construction of a monotone, almost-balanced boolean function on $n$ bits that is resilient to coalitions of size $n^{1-\delta}$, for any $\delta>0$. In fact, our construction is stronger in that it gives an explicit extractor for a generalization of non-oblivious bit-fixing sources on $n$ bits, where some unknown $n-q$ bits are chosen almost $polylog(n)$-wise independently, and the remaining $q=n^{1-\delta}$ bits are chosen by an adversary as an arbitrary function of the $n-q$ bits. The best previous construction, by Viola \cite{Viola14}, achieved $q=n^{1/2 - \delta}$.

Our other main contribution is a reduction showing how such a resilient function gives a two-source extractor. This relies heavily on the new non-malleable extractor of Chattopadhyay, Goyal and Li [CGL15].

Our explicit two-source extractor directly implies an explicit construction of a $2^{(\log \log N)^{O(1)}}$-Ramsey graph over $N$ vertices,
improving bounds obtained by Barak et al. [BRSW12] and matching independent work by Cohen [Coh15b].