Extractors for Sum of Two Sources

Extractors for Sum of Two Sources (via Zoom)

Abstract:  Randomness is a powerful resource in many areas of computer science. However, most of the applications require access to uniform random bits, while sources of randomness in nature are usually imperfect. A solution to this problem is using the notion of a randomness extractor, which is an algorithm that converts imperfect randomness into uniform, independent bits. Ideally, one would hope to construct an extractor that works for every weak source, but it can be proved that such an extractor cannot exist. Therefore, the general goal is to construct extractors which work for a class of sources, assuming some structure. 

In this talk, I will discuss our results on extractors for sumset sources, a class of distributions (on n-bit strings) that can be represented as the sum (bitwise XOR) of two independent sources. Sumset sources are a very general class which contain (and generalize) many well-studied classes of imperfect sources, including independent sources, affine sources and small-space sources. However, prior to this work, even the existence of good sumset extractors was unclear. In this work, we construct the first explicit extractor for sumset sources that work even for very low entropy, and derive interesting applications. Notably, our result implies extractors that can extract randomness from imperfect sources sampled by limited memory algorithms, with the entropy requirement being optimal in the space parameter.

Bio:  Jyun-Jie is a 5th year PhD student at Cornell's CS department being advised by Professor Eshan Chattopadhyay. He is broadly interested in pseudorandomness, complexity theory and cryptography. Prior to joining Cornell, he was a research assistant at Academia Sinica. Prior to Academia Sinica, he received his Bachelor's degree in EECS from National Chiao Tung University.