Towards optimal two-source extractors and Ramsey graphs
Gil Cohen · 2017
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 Ο(logn), which is optimal up to the poly(loglogn) factor. A strong motivation for constructing two-source extractors for low entropy is for Ramsey graphs constructions. Our two-source extractor readily yields a (logn)(logloglogn)Ο(1)-Ramsey graph on n vertices.