  We make progress in the following three problems: 1. Constructing optimal
seeded non-malleable extractors; 2. Constructing optimal privacy amplification
protocols with an active adversary, for any security parameter; 3. Constructing
extractors for independent weak random sources, when the min-entropy is
extremely small (i.e., near logarithmic).
  For the first two problems, the best known non-malleable extractors by
Chattopadhyay, Goyal and Li [CGL16], and by Cohen [Coh16a,Coh16b] all require
seed length and min-entropy at least $\log^2 (1/\epsilon)$, where $\epsilon$ is
the error of the extractor. As a result, the best known explicit privacy
amplification protocols with an active adversary, which achieve 2 rounds of
communication and optimal entropy loss in [Li15c,CGL16], can only handle
security parameter up to $s=\Omega(\sqrt{k})$, where $k$ is the min-entropy of
the shared secret weak random source. For larger $s$ the best known protocol
with optimal entropy loss in [Li15c] requires $O(s/\sqrt{k})$ rounds of
communication.
  In this paper we give an explicit non-malleable extractor that only requires
seed length and min-entropy $\log^{1+o(1)} (n/\epsilon)$, which also yields a
2-round privacy amplification protocol with optimal entropy loss for security
parameter up to $s=k^{1-\alpha}$ for any constant $\alpha>0$.
  For the third problem, previously the best known extractor which supports the
smallest min-entropy due to Li [Li13a], requires min-entropy $\log^{2+\delta}
n$ and uses $O(1/\delta)$ sources, for any constant $\delta>0$. A very recent
result by Cohen and Schulman [CS16] improves this, and constructed explicit
extractors that use $O(1/\delta)$ sources for min-entropy $\log^{1+\delta} n$,
any constant $\delta>0$. In this paper we further improve their result, and
give an explicit extractor that uses $O(1)$ (an absolute constant) sources for
min-entropy $\log^{1+o(1)} n$.
