The main contribution of this work is a construction of a two-source extractor for quasi-logarithmic min-entropy. That is, an extractor for two independent $n$-bit sources with min-entropy $\widetilde{O}(\log{n})$, which is optimal up to the $poly(\log\log{n})$ factor. A strong motivation for constructing two-source extractors for low entropy is for Ramsey graphs constructions. Our two-source extractor readily yields a $(\log{n})^{(\log\log\log{n})^{O(1)}}$-Ramsey graph on $n$ vertices.

Although there has been exciting progress towards constructing $O(\log{n})$-Ramsey graphs in recent years, a line of work that this paper contributes to, it is not clear if current techniques can be pushed so as to match this bound. Interestingly, however, as an artifact of current techniques, one obtains strongly explicit Ramsey graphs, namely, graphs on $n$ vertices where the existence of an edge connecting any pair of vertices can be determined in time $poly(\log{n})$. On top of our strongly explicit construction, in this work, we consider algorithms that output the entire graph in $poly(n)$-time, and make progress towards matching the desired $O(\log{n})$ bound in this setting. In our opinion, this is a natural setting in which Ramsey graphs constructions should be studied.

The main technical novelty of this work lies in an improved construction of an independence-preserving merger (IPM), a variant of the well-studied notion of a merger, which was recently introduced by Cohen and Schulman (FOCS'16). Our construction is based on a new connection to correlation breakers with advice. In fact, our IPM satisfies a stronger and more natural property than that required by the original definition, and we believe it may find further applications.

Added a semi-explicit construction of multi-source extractors. Also, a revised presentation, including a new introduction (and a new title.)

This paper offers the following contributions:

* We construct a two-source extractor for quasi-logarithmic min-entropy. That is, an extractor for two independent $n$-bit sources with min-entropy $\widetilde{O}(\log{n})$. Our construction is optimal up to $\mathrm{poly}(\log\log{n})$ factors and improves upon a recent result by Ben-Aroya, Doron, and Ta-Shma (ECCC'16) that can handle min-entropy $\log{n} \cdot 2^{O(\sqrt{\log\log{n}})}$.

* A central problem in combinatorics is that of constructing $k$-Ramsey graphs on $n$ vertices with $k = O(\log{n})$. Prior to this work, the best construction, which readily follows by the work of Ben-Aroya et al. is for $k = (\log{n})^{2^{O(\sqrt{\log\log\log{n}})}}$. We improve that to $k = (\log{n})^{(\log\log\log{n})^{O(1)}}$.

* We obtain a privacy amplification protocol against active adversaries with security parameter $\lambda = k/(\log{k})^{O(1)}$, where $k$ is the min-entropy of the source shared by the parties. Prior to this work, the security parameter of the best protocols by Chattopadhyay and Li (FOCS'16), and Cohen (FOCS'16), was $k/2^{O(\sqrt{\log\log{k}})}$.

We obtain our results by constructing an improved non-malleable extractor. For $n$-bit sources, when set with error guarantee $\epsilon$, our non-malleable extractor has seed length $d = O(\log{n})+\widetilde{O}(\log(1/\epsilon))$ and can support any min-entropy $\Omega(d)$.

The main technical novelty of this work lies in an improved construction of an independence-preserving merger (IPM) - a variant of the well-studied notion of a merger, that was recently introduced by Cohen and Schulman (FOCS'16). Our construction is based on a new connection to correlation breakers with advice. In fact, our IPM satisfies a stronger and more natural property than that required by the original definition, and we believe it may find further applications.