Pseudorandom generators for combinatorial checkerboards
We define a combinatorial checkerboard to be a function f : {1, . . . , m} (d) -> {1,-1} of the form for some functions f (i) : {1, . . . , m} -> {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 -fools all combinatorial checkerboards with seed length . Previous work by Impagliazzo, Nisan, and Wigderson implies a pseudorandom generator with seed length . Our seed length is better except when 1/epsilon >= d(omega(log d)).
pseudorandom generators combinatorial checkerboards explicit constructions derandomization