UC San Diego

We consider the following problem: for given n,M, produce a sequence X 1,X2,...,Xn of bits that fools every linear test modulo M. We present two constructions of generators for such sequences. For every constant prime power M, the first construction has seed length O M(log(n/∈)), which is optimal up to the hidden constant. (A similar construction was independently discovered by Meka and Zuckerman [MZ]). The second construction works for every M,n, and has seed length O(logn+log(M/∈)log(Mlog(1/∈))). The problem we study is a generalization of the problem of constructing small bias distributions [NN], which are solutions to the M=2 case. We note that even for the case M=3 the best previously known constructions were generators fooling general bounded-space computations, and required O(log2 n) seed length. For our first construction, we show how to employ recently constructed generators for sequences of elements of ℤM that fool small-degree polynomials (modulo M). The most interesting technical component of our second construction is a variant of the derandomized graph squaring operation of [RV]. Our generalization handles a product of two distinct graphs with distinct bounds on their expansion. This is then used to produce pseudorandom-walks where each step is taken on a different regular directed graph (rather than pseudorandom walks on a single regular directed graph as in [RTV, RV]). © 2009 Springer.