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.

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.