Extractors and lower bounds for locally samplable sources

Anindya De, Thomas Watson*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

11 Scopus citations

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 languageEnglish (US)
Article number3
JournalACM Transactions on Computation Theory
Volume4
Issue number1
DOIs
StatePublished - Mar 1 2012

Keywords

  • Extractors
  • Locally samplable sources
  • Lower bounds

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Extractors and lower bounds for locally samplable sources'. Together they form a unique fingerprint.

Cite this