ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR10-176 | 7th January 2013 16:02

Pseudorandom Generators for Combinatorial Shapes

RSS-Feed

Abstract:

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.



Changes to previous version:

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


Paper:

TR10-176 | 15th November 2010 02:03

Pseudorandom Generators for Combinatorial Shapes


Abstract:

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.



ISSN 1433-8092 | Imprint