Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: Explicit Two-source Extractors for Near-logarithmic Min-entropy
event speaker icon
Dean Doron (Tel-Aviv University)
event date icon
Wednesday, 04.01.2017, 12:30
event location icon
Taub 201
In this talk, we show an explicit construction of extractors for two independent sources of near-logaritmic 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.