GUV lossless condenser with logarithmic seed and uniform evaluation
ProvedTimeSpaceMA.shortLosslessCondensercomplexity-theorycondenserspseudorandomness
For each fixed error , a single deterministic polynomial-time evaluator gives a lossless condenser for all input widths and entropy thresholds . For a constant , set . The evaluator maps an -bit input and a uniform -bit seed to bits. For every flat source of cardinality at least , its output is within statistical distance of a probability distribution whose atoms have mass at most . The evaluator receives the input and seed widths in unary. This is the Reed–Solomon lossless condenser with stretch parameter one, padded to the stated lengths.
Preamble
import Definitions.Def_TimeSpaceMA_TUZExtractorComponents
Formal statement
namespace TimeSpaceMA
theorem shortLosslessCondenser (δ : ℝ) (hδ : 0 < δ) (hδ' : δ ≤ 1/8) :
HasShortLosslessCondenser δ := by sorry
end TimeSpaceMASource
Guruswami, Umans and Vadhan, Unbalanced Expanders and Randomness Extractors from Parvaresh–Vardy Codes, JACM 56(4), 2009, Theorems 6.3 and 6.5. https://www.cs.cmu.edu/~venkatg/pubs/papers/PV-condenser.pdf