pseudorandom generators for combinatorial shapes
We construct pseudorandom generators for combinatorial shapes , which substantially generalize combinatorial rectangles, ?-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 ? [m] and a symmetric function h:{0,1} n -> {0,1} such that f(x 1 ,...,x n ) = h(1 A 1 (x 1 ),...,1 A n (x n )). Our generator uses seed length O(log m + log n + log 2 (1/?)) to get error ?. 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 ?-close to the appropriate binomial distribution in statistical distance. 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.
pseudorandom generators limit theorems branching programs small space