Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

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

#### Extractors and Lower Bounds for Locally Samplable Sources

Revision #3
Authors: Anindya De, Thomas Watson
Accepted on: 22nd December 2011 21:18
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
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
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
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.