Towards optimal randomness extractors (Xin Li)

Abstract

Randomness extractors are functions that take as input one or more biased random sources, and output an almost uniform probability distribution.They are fundamental objects in the study of pseudorandomness, and are closely related to other important objects such as error correcting codes and pseudorandom generators. A major challenge here, proposed by Chor and Goldreich in 1985, is to construct explicit extractors for independent biased random sources. Such extractors are useful in distributed computing/cryptography, and give constructions of explicit Ramsey graphs. While one can show the existence of extractors for two independent sources with logarithmic entropy, until 2005 we only know how to build explicit extractors for linear entropy.

Recently, with new connections established between this problem and other problems in distributed computing/cryptography, significant progress has been made in this area, leading to almost optimal constructions. In this talk I will survey some of the important results and techniques, and discuss several open problems for future research.

Time

Speaker

Room