Extractors for Sum of Two Sources (以英文演講)
- 講者廖俊杰 先生 (美國康乃爾大學)
邀請人：鐘楷閔 - 時間2023-08-01 (Tue.) 10:15 ~ 12:30
- 地點資訊所新館101演講廳
摘要
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.
The talk is based on a joint work with Eshan Chattopadhyay in STOC 2022.
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.
The talk is based on a joint work with Eshan Chattopadhyay in STOC 2022.