REVIEW
Multiplicative and Additive Extractors for Low Entropy Samplable Sources Under Reduced Assumptions
Computational Complexity · Submitted 5 Nov 2026 · 13 references
Pith's verdict: Significant, well-written paper that substantially lowers min-entropy thresholds for seedless extractors under standard hardness assumptions. All constructions conditional, but the technical work is rigorous and introduces new machinery.
Why Pith says this
Highlight any text to comment on it.
Referee report
The paper
The paper claims
Three new extractors for samplable sources push the entropy threshold to O(log n) under nondeterministic hardness, matching nonconstructive bounds.
The reading
What carries the argument
The constructions rely on three main ingredients: (1) robust errorless block condensers, which condense entropy from subsources of a samplable joint distribution; (2) errorless condensers, built via an iterative win-win argument that repeatedly splits the source into medium- and light-weight parts; and (3) local correlation breakers, constructed from a seed-extending PRG, a low-degree extension of a hard function, and a two-source non-malleable extractor. The Goldwasser–Sipser set-lower-bound protocol is used to implement polynomial tests with small nondeterministic circuits.
Extended reading notes
Core claim
The paper proves that under the assumption that E is hard for exponential-size nondeterministic circuits, one can construct seedless extractors for samplable distributions with min-entropy as low as k = O(log n) (one bit, constant error), k = n^α (multiplicative extractor outputting k^Ω(1) bits with polynomially small error), and k = polylog(n) (additive extractor outputting almost all entropy with polynomially small error, under Σ₂ hardness). These results dramatically lower the min-entropy threshold compared to prior work such as [TV00], [BSS25], [Sha25a], while using weaker hardness assumptions. The constructions also work for distributions samplable with nondeterministic postselection, a generalization that captures leakage scenarios.
Load-bearing premise
The paper assumes that the complexity class E contains a problem that cannot be solved by nondeterministic circuits of size $2^{{β n}}$ for some constant β > 0; if this assumption is false, all three main constructions collapse.
Editorial extensions
If this is right
- If the nondeterministic hardness assumption is true, then cryptographic protocols can use the multiplicative extractor to select keys from weak random sources while retaining negligible security loss, even when the extractor error is a constant.
- The one-bit extractor matches the probabilistic method, showing that explicit construction can achieve the same parameters for samplable sources under a plausible computational assumption.
- The results provide extractors for the more general model of distributions samplable with postselection, meaning extraction is possible even when information about the sample is leaked via an efficient predicate.
- The errorless condenser construction gives a way to boost entropy in a lossless way for samplable sources, which may be useful for other derandomization tasks.
- Compared to prior work, the min-entropy threshold is lowered from near n to n^α or even O(log n), making extractors practical for sources with much less randomness.
Reading between the lines
- The paper does not provide evidence for the hardness assumptions; if those assumptions were refuted, all constructions would collapse. It would be interesting to see whether any of the results can be based on weaker, still plausible assumptions or on worst-case hardness.
- The iterative win-win construction of errorless condensers uses a delicate decomposition that may be reusable for other pseudorandom objects, such as condensers for more general models of computation.
- The local correlation breaker is built from a two-source non-malleable extractor; improving that construction (e.g., to longer output or lower error) would directly improve the parameters of the extractors.
Original abstract
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 $\mathsf{E}=\mathsf{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 [BGDM, FOCS'23] 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 \textit{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}}$.
The compiled record
The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
The abstract, sentence by sentence
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 $\mathsf{E}=\mathsf{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 [BGDM, FOCS'23] 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 \textit{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}}$.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | 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 $\mathsf{E}=\mathsf{DTIME}(2^{O(n)})$ requires size $2^{\Omega(n)}$ circuits that have oracle access to $\Sigma_6^{\text{P}}$. | background 1.00 | 0.03 | 0.03 | asserted 1.00 |
| s1 | In this paper we give three new explicit constructions of extractors for samplable distributions. | contribution 1.00 | 0.93 | 0.40 | asserted 1.00 |
| s2 | 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. | result 0.64 | 0.95 | 0.17 | asserted 1.00 |
| s3 | 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. | result 0.39 | 0.76 | 0.08 | asserted 1.00 |
| s4 | 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 [BGDM, FOCS'23] that generalizes samplable and recognizable sources). | contribution 0.60 | 0.82 | 0.07 | asserted 1.00 |
| s5 | 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. | contribution 0.55 | 0.96 | 0.12 | asserted 1.00 |
| s6 | 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. | contribution 0.42 | 0.81 | 0.10 | asserted 1.00 |
| s7 | This extractor is also \textit{multiplicative}: a stronger notion suggested in [AASY, Comp. | contribution 0.37 | 0.71 | 0.07 | asserted 0.97 |
| s8 | Complexity'16; Shaltiel, CCC'25] to make extractors for samplable distributions suitable for selecting keys for cryptographic protocols. | interpretation 0.68 | 0.16 | 0.05 | asserted 0.56 |
| s9 | Third, we construct an extractor that extracts almost all the entropy, with polynomially small error, for min-entropy $k=\mathrm{polylog}(n)$. | contribution 0.70 | 0.96 | 0.13 | asserted 1.00 |
| s10 | This result uses hardness for circuits that have oracle access to $\Sigma_2^{\text{P}}$. | method 0.85 | 0.85 | 0.06 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
Figures
Figures reproduced from arXiv:2611.07829 by the authors.
References
Discussion
Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.