Extractors and Lower Bounds for Locally Samplable Sources
Anindya De, Thomas W. Watson · ACM Transactions on Computation Theory · 2012
We consider the problem of extracting randomness from sources that are efficiently samplable, in the sense that each output bit of the sampler only depends on some small number d of the random input bits. As our main result, we construct a deterministic extractor that, given any d -local source with min-entropy k on n bits, extracts Ω ( k 2 / nd ) bits that are 2 −nΩ(1) -close to uniform, provided d ≤ o (log n ) and k ≥ n 2/3+γ (for arbitrarily small constants γ > 0). Using our result, we also improve a result of Viola [2010] who proved a 1/2 − O (1/log n ) statistical distance lower bound for o (log n )-local samplers trying to sample input-output pairs of an explicit boolean function, assuming the samplers use at most n + n 1−δ random bits for some constant δ > 0. Using a different function, we simultaneously improve the lower bound to 1/2 − 2 −nΩ(1) and eliminate the restriction on the number of random bits.