Extractors for Samplable Distributions with Low Min-Entropy

Trevisan and Vadhan (FOCS 2000) introduced the notion of (seedless) extractors for samplable distributions. They showed that under a strong complexity theoretic hardness assumption, there are extractors for samplable distributions with large min-entropy of k = (1 − γ) · n, for some small constant γ>0. Recent work by Ball, Goldin, Dachman-Soled and Mutreja (FOCS 2023) weakened the hardness assumption. However, since the original paper by Trevisan and Vadhan, there has been no improvement in the min-entropy threshold k.

In this paper we give a construction of extractors for samplable distributions with low min-entropy of k = n^{1−γ} for some constant γ, and in particular we achieve k < n/2 (which is a barrier for the construction of Trevisan and Vadhan).

Our extractors are constructed under a hardness assumption that is weaker than the one used by Trevisan and Vadhan, and stronger than that used by Ball, Goldin, Dachman-Soled and Mutreja. Specifically, that there exists a constant β>0, and a problem in E = DTIME(2^O(n)) that cannot be computed by size 2^{βn}  circuits that have an oracle to Σ_5.

Our approach builds on the technique of Trevisan and Vadhan, while introducing new objects and ideas. We introduce and construct two objects: an errorless (seedless) condenser for samplable distributions, and functions that are hard to compute on every samplable distribution with sufficient min-entropy. We use techniques by Shaltiel and Silbak (STOC 2024), as well as additional tools and ideas, to construct the two new objects, under the hardness assumption. We then show how to modify the construction of Trevisan and Vadhan, using these new objects, so that the barrier of k=n/2 can be bypassed, and we can achieve an extractor for samplable distributions with low min-entropy.

This is a joint work with Marshall Ball and Ronen Shaltiel.