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.

Publication type | Inproceedings |

Published in | STOC'11 |

Publisher | ACM |

- Finding Collisions in Interactive Protocols - A Tight Lower Bound on the Round Complexity of Statistically-Hiding Commitments
- Hardness of Reconstructing Multivariate Polynomials over Finite Fields
- The Limits of Two-Party Differential Privacy

> Publications > Pseudorandom Generators for Combinatorial Shapes