Title: Explicit Two-source Extractors for Near-logarithmic Min-entropy
Speaker: Dean Doron, Tel-Aviv University
Date: Wednesday, March 21, 2018 11:00am-12:00pm
Location: CoRE Bldg, Room 301, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
In this talk, we show an explicit construction of extractors for two independent sources of near-logarithmic min-entropy. Previous constructions required either polylog(n) min-entropy or more than two sources. The result extends the breakthrough result of Chattopadhyay and Zuckerman and also uses non-malleable extractors. The main new ingredient is a somewhere-random condenser with a small entropy gap, used as a sampler.
Our construction can be seen as an efficient reduction to constructing non-malleable extractors, so using recent constructions of non-malleable extractors (by Cohen and Li) - we will see how to obtain explicit two-source extractor for O(log n loglog n) min-entropy and constant error.
See: https://sites.google.com/view/dimacs-theory-seminar/home