Name
Abstract | ||
|---|---|---|
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 A1,...,An ⊆ [m] and a symmetric function h:{0,1}n - {0,1} such that f(x1,...,xn) = h(1A1(x1),...,1An(xn)). Our generator uses seed length O(log m + log n + log2(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. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1145/1993636.1993671 | Electronic Colloquium on Computational Complexity |
Keywords | DocType | Volume |
pseudorandom generator,usual kolmogorov distance,combinatorial rectangle,appropriate binomial distribution,combinatorial shape,log n,statistical distance,log m,alternative proof,seed length o | Journal | 42 |
Issue | ISSN | Citations |
3 | 0097-5397 | 6 |
PageRank | References | Authors |
0.48 | 18 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Parikshit Gopalan | 1 | 1186 | 61.52 |
| Raghu Meka | 2 | 485 | 37.05 |
| Omer Reingold | 3 | 3369 | 232.46 |
| David Zucherman | 4 | 2588 | 266.65 |