Shachar Lovett, Omer Reingold, Luca Trevisan, Salil Vadhan
We consider the following problem: for given n,M, produce a sequence X_1,X_2,...,X_n 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/epsilon)), which is optimal up to the hidden constant. (A similar construction was independently discovered by Meka and Zuckerman (RANDOM `09)). The second construction works for every M,n, and has seed length O(log n + log(M/epsilon)*log(M log(1/epsilon))).
The problem we study is a generalization of the problem of constructing small bias distributions (Naor & Naor `93), 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(log^2 n) seed length.
For our first construction, we show how to employ recently constructed generators for sequences of elements of Z_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 [RV05]. 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 [RTV06,RV05].