Extractors and lower bounds for locally samplable sources

Anindya De*, Thomas Watson

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 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 Ω(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.

Original languageEnglish (US)
Title of host publicationApproximation, Randomization, and Combinatorial Optimization
Subtitle of host publicationAlgorithms and Techniques - 14th International Workshop, APPROX 2011 and 15th International Workshop, RANDOM 2011, Proceedings
Pages483-494
Number of pages12
DOIs
StatePublished - Sep 8 2011
Event14th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2011 and the 15th International Workshop on Randomization and Computation, RANDOM 2011 - Princeton, NJ, United States
Duration: Aug 17 2011Aug 19 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6845 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other14th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2011 and the 15th International Workshop on Randomization and Computation, RANDOM 2011
Country/TerritoryUnited States
CityPrinceton, NJ
Period8/17/118/19/11

Keywords

  • extractors
  • locally samplable sources
  • lower bounds

ASJC Scopus subject areas

  • General Computer Science
  • Theoretical Computer Science

Fingerprint

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

Cite this