Recent progress on two-source randomness extractors

A randomness extractor is a deterministic algorithm that converts weak randomness to almost perfect randomness. A weak source of randomness is quantified by its min-entropy, or equivalently, the maximum probability of being guessed correctly. As extracting from a single source is impossible, 2 is the minimum number of sources required.

Optimal 2-source extractors exist by a probabilistic argument but an explicit construction has been a long-standing open problem. In a recent breakthrough, Chattopadhyay and Zuckerman constructed a 2-source extractor for polylogarithmic (in the length of the weak
source) min-entropy, an exponential improvement to the linear min-entropy known before. I will survey this and some follow-up progress and discuss the main open problem of reducing the error from inverse polynomial to negligible.

Key Reference:
– Chattopadhyay and Zuckerman, Explicit Two-Source Extractors and Resilient Functions, STOC 2016.
– Xin Li, Improved Constructions of Two-Source Extractors, arXiv:1508.011.