Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
Extractors and Lower Bounds for Locally Samplable Sources
verfasst von : Anindya De, Thomas Watson
Erschienen in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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^{\Omega(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 (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 −
δ
random bits for some constant
δ
> 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.