Pseudorandom Generators for Combinatorial Shapes

Parikshit Gopalan, Raghu Meka, Omer Reingold, and David Zuckerman

May 2011

We construct pseudorandom generators for combinatorial shapes, which substantially gener-

alize combinatorial rectangles, -biased spaces, 0/1 halfspaces, and 0/1 modular sums.

Our generator uses seed length O(logm + log n + log^2(1/eps)) to get error eps. When m = 2, this gives the fifirst 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. Along the way, we give a generator for combinatorial rectangles with seed length O(log^{1.5} 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.

PDF file | PDF file |

In STOC'11

Publisher ACM

Type | Inproceedings |

> Publications > Pseudorandom Generators for Combinatorial Shapes