Pseudorandom Bit Generators That Fool Modular Sums

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

/

ε

)), 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(

M

log(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

(log

2

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]).