ECCC-Report TR11-037https://eccc.weizmann.ac.il/report/2011/037Comments and Revisions published for TR11-037en-usThu, 22 Dec 2011 21:18:50 +0200
Revision 3
| Extractors and Lower Bounds for Locally Samplable Sources |
Thomas Watson,
Anindya De
https://eccc.weizmann.ac.il/report/2011/037#revision3We 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.Thu, 22 Dec 2011 21:18:50 +0200https://eccc.weizmann.ac.il/report/2011/037#revision3
Revision 2
| Extractors and Lower Bounds for Locally Samplable Sources |
Thomas Watson,
Anindya De
https://eccc.weizmann.ac.il/report/2011/037#revision2We 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.Tue, 12 Jul 2011 18:35:40 +0300https://eccc.weizmann.ac.il/report/2011/037#revision2
Revision 1
| Extractors and Lower Bounds for Locally Samplable Sources |
Thomas Watson,
Anindya De
https://eccc.weizmann.ac.il/report/2011/037#revision1We 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.Mon, 11 Apr 2011 02:32:19 +0300https://eccc.weizmann.ac.il/report/2011/037#revision1
Paper TR11-037
| Extractors and Lower Bounds for Locally Samplable Sources |
Thomas Watson,
Anindya De
https://eccc.weizmann.ac.il/report/2011/037We 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.Fri, 18 Mar 2011 06:53:14 +0200https://eccc.weizmann.ac.il/report/2011/037