Trevisan and Vadhan [TV00] first constructed seedless extractors for distributions samplable by poly-size circuits under the very strong complexity theoretic hardness assumption that $E=DTIME(2^{O(n)})$ is hard for exponential size circuits with oracle access to $\Sigma_6^{P}$. Their construction works when the distribution has large min-entropy $k=(1-\gamma) \cdot n$, for small constant $\gamma>0$.
Recent works build on the approach of [TV00]. [BDGM23] obtain the same result under the weaker assumption that there is a problem in $E$ that is hard for exponential size nondeterministic circuits.
[BSS25] and [Sha25] improve the min-entropy threshold to $k = n^{1-\gamma}$ and $k = n^{\Omega(1)}$ respectively, reinstating oracle access to $\Sigma_i^{P}$ for some $i$ in the assumption.
We introduce a new approach, inspired by constructions of two-source extractors [CZ16,BADTS17], using a new (and incomparable) hardness assumption that only involves deterministic circuits. Our approach reduces the task of constructing extractors for samplable distributions to constructing explicit non-malleable extractors with short seed-length.
Our new assumption has the same flavor as the classic assumption of [IW97] that $E$ is hard for exponential size circuits, and similar to one recently considered in the context of fast derandomization [CT21].
Specifically, we assume that there is a constant $00$, there exists a constant $c'$, and explicit extractor $Ext : \{0,1\}^n \to \{0,1\}$ with error $\eps$, for distributions samplable by circuit of size $n^c$, that have min-entropy $k \ge c' \cdot \log n$.
In light of the best constructions of non-malleable extractors due to Xin Li [Li23], we achieve stronger results regarding extractors for samplable distributions than the previous version. The abstract, intro, and main theorems throughout have been updated accordingly. We are grateful to Mohit Gurumukhani for bringing [Li23] to our attention.
Trevisan and Vadhan [TV00] first constructed seedless extractors for distributions samplable by poly-size circuits under the very strong complexity theoretic hardness assumption that $E=DTIME(2^{O(n)})$ is hard for exponential size circuits with oracle access to $\Sigma_6^{P}$. Their construction works when the distribution has large min-entropy $k=(1-\gamma) \cdot n$, for small constant $\gamma>0$.
Recent works build on the approach of [TV00]. [BDGM23] obtain the same result under the weaker assumption that there is a problem in $\mathsf{E}$ that is hard for exponential size nondeterministic circuits. [BSS25] and [Sha25] improve the min-entropy threshold to $k = n^{1-\gamma}$ and $k = n^{\Omega(1)}$ respectively, reinstating oracle access to $\Sigma_i^{P}$ for some $i$ in the assumption.
We introduce a new approach, inspired by constructions of two-source extractors [CZ16,BADTS17], using a new (and incomparable) hardness assumption that only involves deterministic circuits. Our approach reduces the task of constructing extractors for samplable distributions to constructing explicit non-malleable extractors with short seed-length.
Our new assumption has the same flavor as the classic assumption of [IW97] that $\mathsf{E}$ is hard for exponential size circuits, and similar to one recently considered in the context of fast derandomization [CT21]. Specifically, we assume that there is a constant $0<\alpha<1$ such that for every constant $C_{hard} \ge 1$, there exists a constant $C_{easy}$ and a problem in $DTIME(2^{C_{easy} \cdot n})$ that is not in $DTIME(2^{C_{hard} \cdot n})/2^{\alpha\cdot n}$. The key feature here is that we
allow the ``adversary'' to run in time larger than $2^{n}$ while still only using less than $2^n$ bits of nonuniformity.
Under this assumption, we use currently known constructions of non-malleable extractors to get the following results:
- An extractor for samplable distributions with min-entropy $k$ slightly larger than $n/2$. This is the first construction of any such extractor under an assumption that does not give the adversary nondeterminism.
- An extractor for samplable distributions with min-entropy $k=O(\log n \cdot \log \log n)$ also follows if, in addition to the new assumption, we also have the aforementioned assumption of [BDGM23], namely, that $E$ is hard for exponential size nondeterministic circuits. This is the first construction in the regime of $k \le poly log n$ under any assumption.
We also show that future improvements of the seed length of the best current non-malleable extractors [Li17] would imply the second result without the additional assumption.
Our key observation is that when a given source is samplable, the set of ``bad'' seeds to a non-malleable extractor is efficiently recognizable. We utilize this observation to show that in the constructions of two-source extractors in [CZ16,BADTS17], we can hope to replace the ``second source'' with (the truth table of) a sufficiently hard function. Thus our work reveals an unexpected connection between two-source extractors and extractors for samplable distributions, similar to Trevisan's connection between extractors and PRGs ``in the other direction.''
