Pseudorandom Generators for Combinatorial Shapes

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.

prgcs-full.pdf
PDF file
prgcs-stoc.pdf
PDF file

In  STOC'11

Publisher  ACM

Details

TypeInproceedings
> Publications > Pseudorandom Generators for Combinatorial Shapes