# Pseudorandom Bit Generators

Fooling Modular Sums

Shachar Lovett, Omer Reingold, Luca Trevisan, Salil Vadhan

### Abstract

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

### Versions

- Preliminary version, April 2009. [pdf]
- In
*Proceedings of the 13th International Workshop on Randomization and Computation (RANDOM `09)*, Lecture Notes in Computer Science, pages 615-630. Springer-Verlag, 21-23 August 2009. [pdf][Springer page]

[ back to
Salil Vadhan's research]