Revision #1 Authors: Parikshit Gopalan, Raghu Meka, Omer Reingold, David Zuckerman

Accepted on: 7th January 2013 16:02

Downloads: 764

Keywords:

We 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.

Updated to the final version to appear in SICOMP. Fixes various typos and other minor errors.

TR10-176 Authors: Parikshit Gopalan, Raghu Meka, Omer Reingold, David Zuckerman

Publication: 15th November 2010 02:16

Downloads: 1874

Keywords:

We 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.