Abstract
The breakthrough result of Chattopadhyay and Zuckerman \cite{CZ15} gives a reduction from the construction of explicit non-malleable extractors to the construction of explicit two-source extractors and bipartite Ramsey graphs. However, even assuming the existence of optimal explicit non-malleable extractors only gives a two-source extractor (or a Ramsey graph) for $\poly(\log n)$ entropy, rather than the optimal $O(\log n)$. In this paper we modify the construction to solve the above barrier. Using the currently best explicit non-malleable extractors we get an explicit bipartite Ramsey graphs for sets of size $2^k$, for $k=O(\log n \log\log n)$. Any further improvement in the construction of non-malleable extractors would immediately yield a corresponding two-source extractor. Intuitively, Chattopadhyay and Zuckerman use an extractor as a sampler, and we observe that one could use a weaker object -- a \emph{somewhere-random condenser} with a small entropy gap and a very short seed. We also show how to explicitly construct this weaker object using the Raz \etal error reduction technique \cite{RRV99}, and the constant degree dispersers of Zuckerman that also work against extremely small tests \cite{Zuc06}.