## Abstract

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.

Original language | English (US) |
---|---|

Article number | 3 |

Journal | ACM Transactions on Computation Theory |

Volume | 4 |

Issue number | 1 |

DOIs | |

State | Published - Mar 2012 |

## Keywords

- Extractors
- Locally samplable sources
- Lower bounds

## ASJC Scopus subject areas

- Theoretical Computer Science
- Computational Theory and Mathematics