RRV extractor with polylogarithmic seed and constant entropy loss
ProvedTimeSpaceMA.polylogConstantLossExtractorcomplexity-theoryextractorspseudorandomness
For each fixed error , there are constants and and a uniform polynomial-time extractor for all input widths and thresholds . Put . For every source whose atom probabilities are at most , the output on an independent uniform -bit seed is within statistical distance of uniform on bits. This formulation includes the seed in the output of the strong extractor and allows independent extra seed bits to pad its seed schedule. The evaluator receives the input and seed widths in unary.
Preamble
import Definitions.Def_TimeSpaceMA_TUZExtractorComponents
Formal statement
namespace TimeSpaceMA
theorem polylogConstantLossExtractor (δ : ℝ) (hδ : 0 < δ) (hδ' : δ ≤ 1/8) :
HasPolylogConstantLossExtractor δ := by sorry
end TimeSpaceMASource
Raz, Reingold and Vadhan, Extracting All the Randomness and Reducing the Error in Trevisan’s Extractors, ECCC TR99-046 (1999), Theorem 4. https://eccc.weizmann.ac.il/report/1999/046/