Pseudorandom Generators for Combinatorial Shapes

Pseudorandom Generators for Combinatorial Shapes,Electronic Colloquium on Computational Complexity,Parikshit Gopalan,Raghu Meka,Omer Reingold,David Zu

Pseudorandom Generators for Combinatorial Shapes   (Citations: 1)
BibTex | RIS | RefWorks Download
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 !f0; 1g is an (m;n)-combinatorial shape if there exist sets A1;:::;An [m] and a symmetric function h :f0; 1g n ! f0; 1g such that f(x1;:::;xn) = h(1A1 (x1);:::; 1An (xn)). Our generator uses seed length O(logm + logn + log 2 (1=")) to get error ". When m = 2, this gives the rst generator of seed length O(logn) 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 3=2 n) and error 1=poly(n), matching Lu’s bound [ICALP 1998].
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...Faced with this difficulty, research was focussed on solving special cases of this problem with better seed lengths ([15],[16],[17])...
    • ...In contrast, results in [15], [16], [17] which are directed towards “symmetric functions” use a combination of hash functions and INW generator...

    Anindya De. Pseudorandomness for Permutation and Regular Branching Programs

Sort by: