Abstract
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/\eps)log log (1/\eps)) for error \eps; 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 talk, I'll describe a set of new techniques that 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, our results include the first seeded non-malleable extractor where either the seed length or the entropy requirement can be optimal, further improvements on two source extractors, and the first explicit non-malleable code in the 2-split state model with constant rate, which has been a major goal in the study of non-malleable codes for quite some time. We believe our new techniques can help to eventually obtain completely optimal constructions in the above questions, and may have applications in other settings.