This work is in the research direction discussed in choice NR 420. What I find most appealing in the current work is that it uses the minimal possible assumptions. Indeed, the fact that TV00 used a non-standard that seemed too strong than needed was something that bothered me for decades. The current paper achieves negligible error and small randomness waste wrt sources of very small min-entropy, all under the minimal assumption.
We study the problem of constructing randomness extractors for samplable sources, introduced by Trevisan and Vadhan (FOCS 2000), a natural computational model of imperfect randomness, where the source $\mathbb{X}$ (on $n$ bits) is generated by a polynomial-size circuit. They showed how to extract from sources with min-entropy $(1-\alpha)n$ (for small $\alpha>0$) assuming exponential hardness against $\Sigma_6$-circuits.
A line of recent works has made significant progress, either achieving extraction from such high min-entropy under weaker assumptions (e.g., nondeterministic circuits), or handling polynomially small min-entropy under stronger assumptions (e.g., hardness against $\Sigma_i$-circuits). These works output nearly all the randomness with polynomially small error. In a recent work, Oh and Shaltiel (STOC 2026) constructed extractors that work for logarithmic min-entropy under incomparable assumptions, outputting $1$ random bit with constant error.
Our main result gives an extractor for samplable sources with min-entropy $\poly(log(n))$ with polynomially small error and outputting almost all of the randomness, assuming hardness against nondeterministic circuits. The extractor also works for sources samplable with postselection by nondeterministic circuits. We can further reduce the entropy requirement to $O(\log n)$ at the expense of making the error constant and outputting only $1$ bit, matching the extractor of Oh and Shaltiel (STOC 2026). By prior work of Shaltiel (CCC 2025), our extractors imply hardness against nondeterministic circuits, and thus our assumption is essentially minimal.
See ECCC TR26-089.