Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #3 to TR11-037 | 22nd December 2011 21:18

Extractors and Lower Bounds for Locally Samplable Sources

RSS-Feed




Revision #3
Authors: Anindya De, Thomas Watson
Accepted on: 22nd December 2011 21:18
Downloads: 2808
Keywords: 


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 $\Omega(k^2/nd)$ bits that are $2^{-n^{\Omega(1)}}$-close to uniform, provided $d\leq o(\log n)$ and $k\geq 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.


Revision #2 to TR11-037 | 12th July 2011 18:35

Extractors and Lower Bounds for Locally Samplable Sources





Revision #2
Authors: Anindya De, Thomas Watson
Accepted on: 12th July 2011 18:35
Downloads: 2760
Keywords: 


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 $\Omega(k^2/nd)$ bits that are $2^{-n^{\Omega(1)}}$-close to uniform, provided $d\leq o(\log n)$ and $k\geq 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.


Revision #1 to TR11-037 | 11th April 2011 02:32

Extractors and Lower Bounds for Locally Samplable Sources





Revision #1
Authors: Anindya De, Thomas Watson
Accepted on: 11th April 2011 02:32
Downloads: 2753
Keywords: 


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 $\Omega(k^2/nd)$ bits that are $2^{-n^{\Omega(1)}}$-close to uniform, provided $d\leq o(\log n)$ and $k\geq 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.


Paper:

TR11-037 | 18th March 2011 03:09

Extractors and Lower Bounds for Locally Samplable Sources





TR11-037
Authors: Anindya De, Thomas Watson
Publication: 18th March 2011 06:53
Downloads: 3089
Keywords: 


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 $\Omega(k^2/nd)$ bits that are $2^{-n^{\Omega(1)}}$-close to uniform, provided $d\leq o(\log n)$ and $k\geq 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.



ISSN 1433-8092 | Imprint