Extractors for Samplable Distributions with Polynomially Small Min-Entropy

Trevisan and Vadhan (FOCS 2000) introduced the notion of (seedless) extractors for samplable distributions. They showed that under a very strong complexity theoretic hardness assumption (specifically, that there exists a problem in $\mathrm{E}=$ DTIME $\left(2^{O(n)}\right)$ that cannot be computed by size $2^{\Omega(n)}$ circuits that have an oracle to $\Sigma_{6}^{\mathrm{P}}$) there are extractors for samplable distributions with large min-entropy of $k=(1-\gamma) \cdot n$, for some small constant $\gamma{\gt}0$. Recently, Ball, Shaltiel and Silbak (STOC 2025) were able to reduce the min-entropy threshold to $k=n^{1-\gamma}$. Ball et al., point out that their approach does not work for $k{\lt}\sqrt{n}$ (and this holds even for stronger hardness assumptions, in which 6 is replaced with any other constant). In this paper, we show how to further reduce the minentropy threshold to $k=n^{0.34}\lt \sqrt{n}$ under the same hardness assumption used by Trevisan and Vadhan. More generally, for every positive integer $i \geq 2$, and every $\alpha{\gt}\frac{1}{i}$, we construct an extractor for samplable distributions with min-entropy $k=n^{\alpha}$, under a hardness assumption in which 6 is replaced with $i+3$ (the aforementioned result is a obtained for i = 3). We also provide a multiplicative version of our extractors (under a stronger hardness assumption) addressing an open problem of Ball et al. Our work builds on the approach of Ball et al., who reduced the task of constructing extractors for samplable distributions with min-entropy k, to the task of constructing errorless condensers for samplable distributions with min-entropy k. Our main technical contribution is a new construction of errorless condensers for samplable distributions with $k=n^{\alpha}$ under the hardness assumption stated above, improving upon the minentropy threshold achieved in Ball et al. (which cannot achieve $k\lt \sqrt{n}$). Our insight is that the technique used by Ball et al. to reduce the task of constructing extractors to that of constructing errorless condensers, can itself be used to construct errorless condensers for polynomially small min-entropy when combined with “win-win analysis” approaches that are inspired by some early work on seeded extractors and dispersers. In order to do this, we adapt these approaches from the information theoretic scenario of seeded extractors and dispersers to the computational scenario of errorless condensers for samplable distributions. Index Terms-Randomness extractors, Samplable distributions. In memory of Luca Trevisan. Research supported by ISF grant 1006/23. This research is also co-funded by the European Union (ERC, NFITSC, 101097959). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council. Neither the European Union nor the granting authority can be held responsible for them.