Trevisan strong extractor leaving polylogarithmic residual entropy
ProvedTimeSpaceMA.RRV.nearFullStrongExtractorcomplexity-theoryextractorspseudorandomness
For every fixed error , choose a constant and a deterministic polynomial-time multitape evaluator. For input width and min-entropy threshold , the seed has bits and the payload has bits. For any source whose atoms have mass at most , the joint distribution of an independent uniform seed and its extracted payload has statistical distance at most from uniform. The widths in the evaluator query are encoded in unary. This is the nearly full strong extraction stage, before the entropy recovery step.
Preamble
import Definitions.Def_TimeSpaceMA_RRVNearFull
Formal statement
namespace TimeSpaceMA.RRV
theorem nearFullStrongExtractor (ε : ℝ) (hε : 0 < ε) (hε' : ε ≤ 1/32) :
HasNearFullStrongExtractor ε := by sorry
end TimeSpaceMA.RRVSource
Raz, Reingold and Vadhan, Extracting All the Randomness and Reducing the Error in Trevisan’s Extractors, ECCC TR99-046 (1999), Proposition 26. https://eccc.weizmann.ac.il/report/1999/046/