Extractors for Samplable Distributions from the Two-Source Extractor Recipe

Add to your list(s) Download to your calendar using vCal

• Justin Oh (UT Austin)
• Friday 19 September 2025, 10:00-11:00
• Computer Laboratory, William Gates Building, Room SS03.

If you have a question about this talk, please contact Tom Gur.

A natural model of the sources of randomness one might engineer or obtain in nature is the samplable distribution. Such a distribution is generated by an efficient algorithm or circuit, but may not have much randomness overall, e.g. may not have much entropy. Trevisan and Vadhan [TV00] first introduced this notion, and showed under strong complexity theoretic assumptions that it is possible to extract from such sources. That is, there is an algorithm (an extractor) to convert such a distribution into a nearly uniform distribution, which can then be used in applications such as randomized algorithms and cryptography.

There has been recently renewed interest in this problem, with various recent results building off the initial techniques of [TV00]. The two main questions to address are: What is the weakest complexity theoretic assumption required to construct the extractor? What is the smallest amount of entropy required of the original distribution? In this work, we present a new technique for constructing extractors for samplable distributions, that works for essentially the lowest possible entropy required of the original distribution, and using a “qualitatively” weaker assumption than previous works (albeit technically incomparable). Our work introduces a connection between our problem and the breakthrough construction of two-source extractors by Chattopadhyay and Zuckerman. The approach also provides a novel and direct application of pseudorandom generators, a ubiquitous tool in areas such as derandomization.

This talk is part of the Algorithms and Complexity Seminar series.

This talk is included in these lists:

• Algorithms and Complexity Seminar
• All Talks (aka the CURE list)
• Cambridge talks
• Computer Laboratory, William Gates Building, Room SS03
• Department of Computer Science and Technology talks and seminars
• Interested Talks
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31
• yk449

Note that ex-directory lists are not shown.