PSEUDORANDOM GENERATORS FOR COMBINATORIAL SHAPES

We construct pseudorandom generators for combinatorial shapes, which substantially generalize combinatorial rectangles, epsilon-biased spaces, 0/1 halfspaces, and 0/1 modular sums. A function f : [m](n) -> {0, 1} is an (m, n)-combinatorial shape if there exist sets A(1), ... , A(n) subset of [m] and a symmetric function h : {0, 1}(n) -> {0, 1} such that f(x(1), ... , x(n)) = h(1(A1) (x(1)), ... , 1A(n) (x(n))). Our generator uses seed-length O(logm + logn + log(2)(1/epsilon)) to get error epsilon. When m = 2, this gives the first generator of seed-length O(log n) that 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 from 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.