Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR10-168 | 7th February 2012 03:12

Pseudorandom Generators for Combinatorial Checkerboards

RSS-Feed




Revision #2
Authors: Thomas Watson
Accepted on: 7th February 2012 03:12
Downloads: 2539
Keywords: 


Abstract:

We define a combinatorial checkerboard to be a function $f:\{1,\ldots,m\}^d\to\{1,-1\}$ of the form $f(u_1,\ldots,u_d)=\prod_{i=1}^df_i(u_i)$ for some functions $f_i:\{1,\ldots,m\}\to\{1,-1\}$. This is a variant of combinatorial rectangles, which can be defined in the same way but using $\{0,1\}$ instead of $\{1,-1\}$. We consider the problem of constructing explicit pseudorandom generators for combinatorial checkerboards. This is a generalization of small-bias generators, which correspond to the case $m=2$.

We construct a pseudorandom generator that $\epsilon$-fools all combinatorial checkerboards with seed length $O\bigl(\log m+\log d\cdot\log\log d+\log^{3/2}\frac{1}{\epsilon}\bigr)$. Previous work by Impagliazzo, Nisan, and Wigderson implies a pseudorandom generator with seed length $O\bigl(\log m+\log^2d+\log d\cdot\log\frac{1}{\epsilon}\bigr)$. Our seed length is better except when $\frac{1}{\epsilon}\geq d^{\omega(\log d)}$.


Revision #1 to TR10-168 | 20th February 2011 01:04

Pseudorandom Generators for Combinatorial Checkerboards





Revision #1
Authors: Thomas Watson
Accepted on: 20th February 2011 01:04
Downloads: 2233
Keywords: 


Abstract:

We define a combinatorial checkerboard to be a function $f:\{1,\ldots,m\}^d\to\{1,-1\}$ of the form $f(u_1,\ldots,u_d)=\prod_{i=1}^df_i(u_i)$ for some functions $f_i:\{1,\ldots,m\}\to\{1,-1\}$. This is a variant of combinatorial rectangles, which can be defined in the same way but using $\{0,1\}$ instead of $\{1,-1\}$. We consider the problem of constructing explicit pseudorandom generators for combinatorial checkerboards. This is a generalization of small-bias generators, which correspond to the case $m=2$.

We construct a pseudorandom generator that $\epsilon$-fools all combinatorial checkerboards with seed length $O\bigl(\log m+\log d\cdot\log\log d+\log^{3/2}\frac{1}{\epsilon}\bigr)$. Previous work by Impagliazzo, Nisan, and Wigderson implies a pseudorandom generator with seed length $O\bigl(\log m+\log^2d+\log d\cdot\log\frac{1}{\epsilon}\bigr)$. Our seed length is better except when $\frac{1}{\epsilon}\geq d^{\omega(\log d)}$.


Paper:

TR10-168 | 9th November 2010 22:34

Pseudorandom Generators for Combinatorial Checkerboards





TR10-168
Authors: Thomas Watson
Publication: 9th November 2010 23:44
Downloads: 3146
Keywords: 


Abstract:

We define a combinatorial checkerboard to be a function $f:\{1,\ldots,m\}^d\to\{1,-1\}$ of the form $f(u_1,\ldots,u_d)=\prod_{i=1}^df_i(u_i)$ for some functions $f_i:\{1,\ldots,m\}\to\{1,-1\}$. This is a variant of combinatorial rectangles, which can be defined in the same way but using $\{0,1\}$ instead of $\{1,-1\}$. We consider the problem of constructing explicit pseudorandom generators for combinatorial checkerboards. This is a generalization of small-bias generators, which correspond to the case $m=2$.

We construct a pseudorandom generator that $\epsilon$-fools all combinatorial checkerboards with seed length $O\bigl(\log m+\log d\cdot\log\log d+\log^{3/2}\frac{1}{\epsilon}\bigr)$. Previous work by Impagliazzo, Nisan, and Wigderson implies a pseudorandom generator with seed length $O\bigl(\log m+\log^2d+\log d\cdot\log\frac{1}{\epsilon}\bigr)$. Our seed length is better except when $\frac{1}{\epsilon}\geq d^{\omega(\log d)}$.



ISSN 1433-8092 | Imprint