Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > COMBINATORIAL RECTANGLES:
Reports tagged with combinatorial rectangles:
TR10-176 | 15th November 2010
Parikshit Gopalan, Raghu Meka, Omer Reingold, David Zuckerman

Pseudorandom Generators for Combinatorial Shapes

Revisions: 1

We construct pseudorandom generators for combinatorial shapes, which substantially generalize combinatorial rectangles, small-bias spaces, 0/1 halfspaces, and 0/1 modular sums. A function f:[m]^n \rightarrow \{0,1\}^n is an (m,n)-combinatorial shape if there exist sets A_1,\ldots,A_n \subseteq [m] and a symmetric function h:\{0,1\}^n \rightarrow \{0,1\} such that f(x_1,\ldots,x_n) = h(1_{A_1} (x_1),\ldots,1_{A_n}(x_n)). Our ... more >>>




ISSN 1433-8092 | Imprint