Skip to main content
eScholarship
Open Access Publications from the University of California

Pseudorandom bit generators that fool modular sums

  • Author(s): Lovett, S
  • Reingold, O
  • Trevisan, L
  • Vadhan, S
  • et al.

Published Web Location

https://pdfs.semanticscholar.org/368a/ba9b9d76e7cf70913aa2bc2747e964c28e2e.pdf
No data is associated with this publication.
Abstract

We consider the following problem: for given n,M, produce a sequence X 1,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 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(logn+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 ℤ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]). © 2009 Springer.

Many UC-authored scholarly publications are freely available on this site because of the UC Academic Senate's Open Access Policy. Let us know how this access is important for you.

Item not freely available? Link broken?
Report a problem accessing this item