In this paper we give improved constructions of several central objects in the literature of randomness extraction and tamper-resilient cryptography. Our main results are:

(1) An explicit seeded non-malleable extractor with error \epsilon and seed length d=O(\log n)+O(\log(1/\epsilon)\log \log (1/\epsilon)), that supports min-entropy k=\Omega(d) and outputs \Omega(k) bits. Combined with the protocol in \cite{DW09}, this gives a two round privacy amplification protocol with optimal entropy loss in the presence of an active adversary, for all security parameters up to \Omega(k/\log k), where k is the min-entropy of the shared weak random source. Previously, the best known seeded non-malleable extractors require seed length and min-entropy O(\log n)+\log(1/\epsilon)2^{O{\sqrt{\log \log (1/\epsilon)}}} \cite{CL16, Coh16}, and only give two round privacy amplification protocols with optimal entropy loss for security parameter up to k/2^{O(\sqrt{\log k})}.

(2) An explicit non-malleable two-source extractor for min-entropy k \geq (1-\gamma)n, some constant \gamma>0, that outputs \Omega(k) bits with error 2^{-\Omega(n/\log n)}. We further show that we can efficiently uniformly sample from the pre-image of any output of the extractor. Combined with the connection in \cite{CG14b} this gives a non-malleable code in the two-split-state model with relative rate \Omega(1/\log n). This exponentially improves previous constructions, all of which only achieve rate n^{-\Omega(1)}.\footnote{The work of Aggarwal et. al \cite{ADKO15} had a construction which ``achieves" constant rate, but recently the author found an error in their proof.}

(3) Combined with the techniques in \cite{BDT16}, our non-malleable extractors give a two-source extractor for min-entropy O(\log n \log \log n), which also implies a K-Ramsey graph on N vertices with K=(\log N)^{O(\log \log \log N)}. Previously the best known two-source extractor in \cite{BDT16} requires min-entropy \log n 2^{O(\sqrt{\log n})}, which gives a Ramsey graph with K=(\log N)^{2^{O(\sqrt{\log \log \log N})}}. We further show a way to reduce the problem of constructing seeded s-source non-malleable extractors to the problem of constructing non-malleable (s+1)-source extractors. Using the non-malleable 10-source extractor with optimal error in \cite{CZ14}, we obtain a seeded non-malleable 9-source extractor with optimal seed length, which in turn gives a 10-source extractor for min-entropy O(\log n). Previously the best known extractor for such min-entropy requires O(\log \log n) sources \cite{CohL16}.

Independent of our work, Cohen \cite{Cohen16} obtained similar results to (1) and the two-source extractor, except the dependence on \epsilon is \log(1/\epsilon) (\log \log (1/\epsilon))^{O(1)} and the two-source extractor requires min-entropy \log n (\log \log n)^{O(1)}.