Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Pseudorandom Generators for Combinatorial Shapes

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

Abstract

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 + log2(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(log1.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.

Details

Publication typeInproceedings
Published inSTOC'11
PublisherACM
> Publications > Pseudorandom Generators for Combinatorial Shapes