|Date: Friday, March 25, 2016
Location: 3725 BBB (10:30 AM to 11:30 AM)
Title: Recent progress on two-source randomness extractors
Abstract: 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.
Speaker: Yaoyun Shi
Event Organizer: schoeneb