Trevisan and Vadhan [TV, FOCS'00] constructed (seedless) extractors for distributions samplable by poly-size circuits that have very high min-entropy, under the very strong complexity theoretic hardness assumption that $\text{E}=\text{DTIME}(2^{O(n)})$ requires size $2^{\Omega(n)}$ circuits that have oracle access to $\Sigma_6^{\text{P}}$. In this paper we give three new explicit constructions of extractors for samplable distributions.
First, we construct an extractor that extracts one bit, with constant error, for min-entropy $k=O(\log n)$, which matches the non-constructive probabilistic argument. This result uses hardness for nondeterministic circuits, and achieves the same parameters as the recent extractor of Oh and Shaltiel [OS, STOC'26] under an incomparable hardness assumption. In contrast to the extractor of [OS26], our extractor (and, similarly, the constructions below) also works for the more general class of distributions samplable with postselection (a model introduced by [BGDM23] that generalizes samplable and recognizable sources).
Second, we construct an extractor that extracts almost all the entropy, with polynomially small error, for min-entropy $k=n^{\alpha}$, where $\alpha>0$ is an arbitrary constant. This result also uses hardness for nondeterministic circuits, and significantly improves upon the recent extractor of [Shaltiel, FOCS'25] which required a much stronger assumption. This extractor is also multiplicative: a stronger notion suggested in [AASY, Comp. Complexity'16; Shaltiel, CCC'25] to make extractors for samplable distributions suitable for selecting keys for cryptographic protocols.
Third, we construct an extractor that extracts almost all the entropy, with polynomially small error, for min-entropy $k=\mathrm{polylog}(n)$. This result uses hardness for circuits that have oracle access to $\Sigma_2^{\text{P}}$.
Prior to this work, the lowest min-entropy threshold $k$ that was achieved using hardness for nondeterministic circuits (or even circuits with oracle access to $\Sigma_2^{\text{P}}$) was larger than $0.99n$ [BGDM, FOCS'23]. Our results significantly improve both the min-entropy threshold and the hardness assumptions compared to all past work that extracts more than one bit.
Our constructions build upon earlier work [TV, FOCS'00; BGDM, FOCS'23; BSS, STOC'25; Shaltiel, FOCS'25] while introducing several new ideas: (1) We simplify and build upon the ideas of [BGDM, FOCS'23] to construct our extractors under nondeterministic hardness. (2) We introduce a notion of robust errorless condensers and construct and use them to obtain our multiplicative extractors. (3) We adapt the two-source extractor recipe from [CZ, Ann. of Mathematics'19] to construct our additive extractors. We do this by constructing and using a correlation breaker against small circuits. Our correlation breaker extends recent constructions of non-malleable extractors against small circuits [BDL, CRYPTO'22; BD, CRYPTO'25].
