Seminars & Colloquia Calendar

Download as iCal file

DIMACS Theory of Computing Seminar

Explicit two-source extractors for near-logarithmic min-entropy

Dean Doron - Tel-Aviv University

Location:  CoRE 301
Date & time: Wednesday, 21 March 2018 at 11:00AM - 12:00PM

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.

Special Note to All Travelers

Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.

Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.