ECCC-Report TR10-176https://eccc.weizmann.ac.il/report/2010/176Comments and Revisions published for TR10-176en-usMon, 07 Jan 2013 16:02:36 +0200
Revision 1
| Pseudorandom Generators for Combinatorial Shapes |
Parikshit Gopalan,
Raghu Meka,
Omer Reingold,
David Zuckerman
https://eccc.weizmann.ac.il/report/2010/176#revision1We construct pseudorandom generators for combinatorial shapes, which substantially generalize combinatorial rectangles, small-bias spaces, 0/1 halfspaces, and 0/1 modular sums. A function $f:[m]^n \rightarrow \{0,1\}^n$ is an $(m,n)$-combinatorial shape if there exist sets $A_1,\ldots,A_n \subseteq [m]$ and a symmetric function $h:\{0,1\}^n \rightarrow \{0,1\}$ such that $f(x_1,\ldots,x_n) = h(1_{A_1} (x_1),\ldots,1_{A_n}(x_n))$. Our generator uses seed length $O(\log m + \log n + \log^2(1/\epsilon))$ to get error $\epsilon$. When $m =2$, this gives the first generator of seed length $O(\log n)$ which fools all weight-based tests, meaning that the distribution of the weight of any subset is $\epsilon$-close to the appropriate binomial distribution in statistical distance. Along the way, we give a generator for combinatorial rectangles with seed length $O(\log^{3/2}n)$ and error $1/poly(n)$, matching Lu's bound [ICALP 1998].
For our proof we give a simple lemma which allows us to convert closeness in Kolmogorov (cdf) distance to closeness in statistical distance. As a corollary of our technique, we give an alternative proof of a powerful variant of the classical central limit theorem showing convergence in statistical distance, instead of the usual Kolmogorov distance.
Mon, 07 Jan 2013 16:02:36 +0200https://eccc.weizmann.ac.il/report/2010/176#revision1
Paper TR10-176
| Pseudorandom Generators for Combinatorial Shapes |
Parikshit Gopalan,
Raghu Meka,
Omer Reingold,
David Zuckerman
https://eccc.weizmann.ac.il/report/2010/176We construct pseudorandom generators for combinatorial shapes, which substantially generalize combinatorial rectangles, small-bias spaces, 0/1 halfspaces, and 0/1 modular sums. A function $f:[m]^n \rightarrow \{0,1\}^n$ is an $(m,n)$-combinatorial shape if there exist sets $A_1,\ldots,A_n \subseteq [m]$ and a symmetric function $h:\{0,1\}^n \rightarrow \{0,1\}$ such that $f(x_1,\ldots,x_n) = h(1_{A_1} (x_1),\ldots,1_{A_n}(x_n))$. Our generator uses seed length $O(\log m + \log n + \log^2(1/\epsilon))$ to get error $\epsilon$. When $m =2$, this gives the first generator of seed length $O(\log n)$ which fools all weight-based tests, meaning that the distribution of the weight of any subset is $\epsilon$-close to the appropriate binomial distribution in statistical distance. Along the way, we give a generator for combinatorial rectangles with seed length $O(\log^{3/2}n)$ and error $1/poly(n)$, matching Lu's bound [ICALP 1998].
For our proof we give a simple lemma which allows us to convert closeness in Kolmogorov (cdf) distance to closeness in statistical distance. As a corollary of our technique, we give an alternative proof of a powerful variant of the classical central limit theorem showing convergence in statistical distance, instead of the usual Kolmogorov distance.
Mon, 15 Nov 2010 02:16:29 +0200https://eccc.weizmann.ac.il/report/2010/176