We consider the following problem: for given
n,
M, produce a sequence
X1,
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
OM(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(log
n + 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
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]).