Date: Friday, March 25, 2016
Location: 3725 BBB (10:30 AM to 11:30 AM)
Title: Recent progress on twosource 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 minentropy, 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 2source extractors exist by a probabilistic argument but an explicit construction has been a longstanding open problem. In a recent breakthrough, Chattopadhyay and Zuckerman constructed a 2source extractor for polylogarithmic (in the length of the weak source) minentropy, an exponential improvement to the linear minentropy known before. I will survey this and some followup progress and discuss the main open problem of reducing the error from inverse polynomial to negligible.
Key Reference:  Chattopadhyay and Zuckerman, Explicit TwoSource Extractors and Resilient Functions, STOC 2016.  Xin Li, Improved Constructions of TwoSource Extractors, arXiv:1508.011.
Files:
Speaker: Yaoyun Shi
Institution: UM
Event Organizer: schoeneb
