  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)$.
  (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)}$. 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)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)}$. We also 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)}$.
