In an influential paper, Trevisan and Vadhan (FOCS 2000) introduced the notion of (seedless) extractors for samplable distributions (namely, distributions that can be sampled by a poly-size circuit). Trevisan and Vadhan showed that under a strong complexity theoretic hardness assumption, there are extractors for samplable distributions with large min-entropy of $k=(1-\gamma) \cdot n$, for some small constant $\gamma>0$.
Recently, there has been significant progress in this area, and extractors for samplable distributions with much lower min-entropy were constructed.
In the talk, I will explain the motivation for extractors for samplable distributions, and the relation of this area to the well known area of worst-case to average-case hardness amplification. I will give a high level overview of the Trevisan-Vadhan construction, and will also explain some of the recent constructions.
This talk is based on several recent joint works with Marshall Ball, Justin Oh and Jad Silbak.
