The recent line of study on randomness extractors has been a great success, resulting in exciting new techniques, new connections, and breakthroughs to long standing open problems in several seemingly different topics. These include seeded non-malleable extractors, privacy amplification protocols with an active adversary, independent source extractors (and explicit Ramsey graphs), and non-malleable codes in the split state model. Previously, the best constructions are given in \cite{Li17}: seeded non-malleable extractors with seed length and entropy requirement $O(\log n+\log(1/\epsilon)\log \log (1/\epsilon))$ for error $\epsilon$; two-round privacy amplification protocols with optimal entropy loss for security parameter up to $\Omega(k/\log k)$, where $k$ is the entropy of the shared weak source; two-source extractors for entropy $O(\log n \log \log n)$; and non-malleable codes in the $2$-split state model with rate $\Omega(1/\log n)$. However, in all cases there is still a gap to optimum and the motivation to close this gap remains strong.

In this paper, we introduce a set of new techniques to further push the frontier in the above questions. Our techniques lead to improvements in all of the above questions, and in several cases partially optimal constructions. This is in contrast to all previous work, which only obtain close to optimal constructions. Specifically, we obtain:
\begin{enumerate}
\item A seeded non-malleable extractor with seed length $O(\log n)+\log^{1+o(1)}(1/\epsilon)$ and entropy requirement $O(\log \log n+\log(1/\epsilon))$, where the entropy requirement is asymptotically optimal by a recent result of Gur and Shinkar \cite{GurS17}; \item A two-round privacy amplification protocol with optimal entropy loss for security parameter up to $\Omega(k)$, which solves the privacy amplification problem completely;\footnote{Except for the communication complexity, which is of secondary concern to this problem.} \item A two-source extractor for entropy $O(\frac{\log n \log \log n}{\log \log \log n})$, which also gives an explicit Ramsey graph on $N$ vertices with no clique or independent set of size $(\log N)^{O(\frac{\log \log \log N}{\log \log \log \log N})}$; and \item The first explicit non-malleable code in the $2$-split state model with \emph{constant} rate, which has been a major goal in the study of non-malleable codes for quite some time. One small caveat is that the error of this code is only (an arbitrarily small) constant, but we can also achieve negligible error with rate $\Omega(\log \log \log n/\log \log n)$, which already improves the rate in \cite{Li17} exponentially.
\end{enumerate}
We believe our new techniques can help to eventually obtain completely optimal constructions in the above questions, and may have applications in other settings.

Added new results about non-malleable codes.

The recent line of study on randomness extractors has been a great success, resulting in exciting new techniques, new connections, and breakthroughs to long standing open problems in the following five seemingly different topics: seeded non-malleable extractors, privacy amplification protocols with an active adversary, independent source extractors (and explicit Ramsey graphs), non-malleable independent source extractors, and non-malleable codes in the split state model. Two key ingredients used in these works are correlation breakers and independence preserving mergers. By giving very efficient constructions of these two objects, we now have close to optimal solutions to the above five problems \cite{Li17}: seeded non-malleable extractors with seed length and entropy requirement $O(\log n+\log(1/\epsilon)\log \log (1/\epsilon))$ for error $\epsilon$; two-round privacy amplification protocols with optimal entropy loss for security parameter up to $\Omega(k/\log k)$, where $k$ is the entropy of the shared weak source; two-source extractors for entropy $O(\log n \log \log n)$; non-malleable two-source extractors for entropy $(1-\gamma)n$ with error $2^{-\Omega(n/\log n)}$; and non-malleable codes in the $2$-split state model with rate $\Omega(1/\log n)$. However, in all cases there is still a small gap to optimum and the motivation to close this gap remains strong. On the other hand, previous techniques seem to have reached their limit and insufficient for this purpose.

In this paper we introduce new techniques to recycle the entropy used in correlation breakers and independence preserving mergers. This allows us to break the barriers of previous techniques and give further improvements to the above problems. Specifically, we obtain the following results: (1) a seeded non-malleable extractor with seed length $O(\log n)+\log^{1+o(1)}(1/\epsilon)$ and entropy requirement $O(\log \log n+\log(1/\epsilon))$, where the entropy requirement is asymptotically optimal by a recent result of Gur and Shinkar \cite{GurS18}; (2) a two-round privacy amplification protocol with optimal entropy loss for security parameter up to $\Omega(k)$, which solves the privacy amplification problem completely;\footnote{Except for the communication complexity, which is of secondary concern to this problem.} (3) a two-source extractor for entropy $O(\frac{\log n \log \log n}{\log \log \log n})$, which also gives an explicit Ramsey graph on $N$ vertices with no clique or independent set of size $(\log N)^{O(\frac{\log \log \log N}{\log \log \log \log N})}$;
(4) a non-malleable two-source extractor for entropy $(1-\gamma)n$ with error $2^{-\Omega(n \log \log n/\log n)}$; and (5) non-malleable codes in the $2$-split state model with rate $\Omega(\log \log n/\log n)$. Some of our techniques are similar in spirit to what has been done in previous constructions of pseudorandom generators for small space computation \cite{Nisan92, NisanZ96}, and we believe they can be a promising way to eventually obtain optimal constructions to the five problems mentioned above.