Seminar Event Detail


Theoretical Computer Science

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.

Files:


Speaker:  Yaoyun Shi
Institution:  U-M

Event Organizer:      schoeneb

 

Edit this event (login required).
Add new event (login required).
For access requests and instructions, contact math-webmaster@umich.edu

Back to previous page
Back to UM Math seminars/events page.