How AI is applied across API Evangelist and APIs.io. Read my AI disclosure →
API Evangelist API Evangelist
Discovery
Learnings
Guidance
Toolbox
Alignment
API Evangelist LLC

Multiplicative and Additive Extractors for Low Entropy Samplable Sources Under Reduced Assumptions

calendar_today November 5, 2026 domain machinelibrary-ai

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^{Ω(n)}$ circuits that have oracle access to $Σ_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.

open_in_new Read original post