TY - GEN
T1 - Extractors and lower bounds for locally samplable sources
AU - De, Anindya
AU - Watson, Thomas
PY - 2011/9/8
Y1 - 2011/9/8
N2 - 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 Ω(k2/nd) bits that are 2 -nΩ(1)-close to uniform, provided d ≤ o(log n) and k ≥ n2/3+γ (for arbitrarily small constants γ > 0). Using our result, we also improve a result of Viola (FOCS 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 + n1-δ 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.
AB - 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 Ω(k2/nd) bits that are 2 -nΩ(1)-close to uniform, provided d ≤ o(log n) and k ≥ n2/3+γ (for arbitrarily small constants γ > 0). Using our result, we also improve a result of Viola (FOCS 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 + n1-δ 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.
KW - extractors
KW - locally samplable sources
KW - lower bounds
UR - http://www.scopus.com/inward/record.url?scp=80052377551&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=80052377551&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-22935-0_41
DO - 10.1007/978-3-642-22935-0_41
M3 - Conference contribution
AN - SCOPUS:80052377551
SN - 9783642229343
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 483
EP - 494
BT - Approximation, Randomization, and Combinatorial Optimization
T2 - 14th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2011 and the 15th International Workshop on Randomization and Computation, RANDOM 2011
Y2 - 17 August 2011 through 19 August 2011
ER -