Revision #3 Authors: Anindya De, Thomas Watson

Accepted on: 22nd December 2011 21:18

Downloads: 1863

Keywords:

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 Authors: Anindya De, Thomas Watson

Accepted on: 12th July 2011 18:35

Downloads: 1828

Keywords:

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 Authors: Anindya De, Thomas Watson

Accepted on: 11th April 2011 02:32

Downloads: 1888

Keywords:

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.

TR11-037 Authors: Anindya De, Thomas Watson

Publication: 18th March 2011 06:53

Downloads: 2237

Keywords: