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

Speaker: Dean Doron , Tel-Aviv University

Date: Wednesday, March 15, 2017

Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: 32-G575

Event Type:

Room Description:

Host: Pritish Kamath and Akshay Degwekar, CSAIL MIT

Contact: Rebecca Yadegar, ryadegar@csail.mit.edu

Relevant URL:

Speaker URL: None

Speaker Photo:
None

Reminders to: seminars@csail.mit.edu, theory-seminars@csail.mit.edu

Reminder Subject: TALK: Dean Doron:Explicit two-source extractors for near-logarithmic min-entropy

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 very 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.

Research Areas:

Impact Areas:

See other events that are part of the Algorithms and Complexity Seminar Series 2016/2017.

Created by Rebecca Yadegar at Wednesday, February 22, 2017 at 6:55 PM.