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, there are extractors for samplable distributions with large min-entropy of $k=(1-\gamma) \cdot n$, for some small constant $\gamma>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-\gamma}$ for some constant $\gamma>0$, and in particular we achieve $k0$, and a problem in $\E=\DTIME(2^{O(n)})$ that cannot be computed by size $2^{\beta n}$ circuits that have an oracle to $\Sigma_5^{\P}$.

(See full abstract in PDF file).