@conference {634704,
	title = {Pseudorandom bit generators that fool modular sums},
	booktitle = {Proceedings of the 13th International Workshop on Randomization and Computation (RANDOM {\textquoteleft}09), Lecture Notes in Computer Science},
	volume = {5687},
	year = {2009},
	pages = {615-630},
	publisher = {Springer-Verlag},
	organization = {Springer-Verlag},
	abstract = {
	We consider the following problem: for given\&nbsp;\(n, M,\) produce a sequence\&nbsp;\(X_1, X_2, . . . , X_n\)\&nbsp;of\&nbsp;bits\&nbsp;that fools every linear test modulo\&nbsp;\(M\). We present two constructions of generators for such sequences. For every constant prime power\&nbsp;\(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 [MZ]). The second construction works for every\&nbsp;\(M, n,\) and has seed length\&nbsp;\(O(\log n + \log(M/\epsilon) \log( M \log(1/\epsilon)))\).



	The problem we study is a generalization of the problem of constructing\&nbsp;small bias\&nbsp;distributions [NN], which are solutions to the\&nbsp;\(M=2\)\&nbsp;case. We note that even for the case\&nbsp;\(M=3\) the best previously known con- structions were generators fooling general bounded-space computations, and required\&nbsp;\(O(\log^2 n)\) seed length.



	For our first construction, we show how to employ recently constructed generators for sequences of elements of\&nbsp;\(\mathbb{Z}_M\)\&nbsp;that fool small-degree polynomials modulo\&nbsp;\(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]).

},
	url = {https://link.springer.com/chapter/10.1007/978-3-642-03685-9_46},
	author = {Shachar Lovett and Omer Reingold and Luca Trevisan and Salil Vadhan}
}
