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 Omega(k^2d) bits that are 2^{-n^{Omega(1)}}-close to uniform, provided dleq o(log n) and kgeq n^{2/3+gamma} (for arbitrarily small constants gamma>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+n^{1-delta} random bits for some constant delta>0. Using a different function, we simultaneously improve the lower bound to 1/2-2^{-n^{Omega(1)}} and eliminate the restriction on the number of random bits
展开▼
