Explicit padded constant-loss extractor for finite flat sources
ProvedTimeSpaceMA.constantLossFlatExtractorcomplexity-theoryextractorspseudorandomness
Fix an error . There are fixed constants and and one deterministic polynomial-time evaluator. For every , threshold , and seed width with , the evaluator maps an -bit input and a uniform -bit seed to bits. Here is binary length. Its output when the input is uniform on any set of at least points has statistical distance at most from uniform.
This is the flat-source specialization of the constant-entropy-loss extractor of Corollary 5.8(2), with the seed width supplied as a parameter. Independent extra seed bits can be carried into the output to preserve the error and realize the specified width. The evaluator runs in polynomial time in the encoded query, which includes the two widths in unary.
Preamble
import Definitions.Def_TimeSpaceMA_TUZExtractor
Formal statement
namespace TimeSpaceMA
open Turing.MultiTapeTM
/-- Corollary 5.8(2) of TUZ, with the seed padded to a supplied width and the
finite statistical-distance property restricted to flat sources. -/
theorem constantLossFlatExtractor (ε : ℝ) (hε : 0 < ε) (hε' : ε ≤ 1/4) :
∃ (A Δ : ℕ) (extract : ExtractorInput → ℕ),
0 < A ∧ ComputableInPolyTime extract encExtractorInput encNat ∧
∀ n k t : ℕ, 1 ≤ n → k ≤ n → A*(n.size+k.size^4) ≤ t → Δ ≤ k+t →
∀ S : Finset (Fin (2^n)), 2^k ≤ S.card →
FlatExtractorEvents (extractorEdge extract Δ n k t) S ε := by sorry
end TimeSpaceMA
Source
Ta-Shma, Umans and Zuckerman, Lossless Condensers, Unbalanced Expanders, and Extractors, Combinatorica 27 (2007), Corollary 5.8(2), PDF p. 22, https://www.cs.tau.ac.il/~amnon/Papers/TUZ.C07.pdf