We construct pseudorandom generators with improved seed length for
several classes of tests. First we consider the class of read-once
polynomials over GF(2) in $m$ variables. For error $\e$ we obtain seed
length $\tilde O (\log(m/\e)) \log(1/\e)$, where $\tilde O$ hides lower-order
terms. This is optimal up to the factor $\tilde O(\log(1/\e))$. The previous
best seed length was polylogarithmic in $m$ and $1/\e$.

Second we consider product tests $f\colon \zo^m \to \C_{\le 1}$. These
tests are the product of $k$ functions $f_i\colon \zo^n \to \C_{\le 1}$,
where the inputs of the $f_i$ are disjoint subsets of the $m$ variables and
$\C_{\le 1}$ is the complex unit disk. Here we obtain seed length $n \cdot
\poly \log (m/\e)$. This implies better generators for other classes of tests.
If moreover the $f_i$ have outputs independent of $n$ and $k$ (e.g.,
$\pmone$) then we obtain seed length $\tilde O(n + \log(k/\e)) \log(1/\e)$.
This is again optimal up to the factor $\tilde O(\log 1/\e)$, while the
previous best seed length was $\ge \sqrt k$.

A main component of our proofs is showing that these classes of tests are
fooled by almost $d$-wise independent distributions perturbed with noise.

Improved bounds for bounded independence plus noise, and changes to exposition

We construct pseudorandom generators with improved seed length for
several classes of tests. First we consider the class of read-once
polynomials over GF(2) in $m$ variables. For error $\e$ we obtain seed
length $\tilde O (\log(m/\e)) \log(1/\e)$, where $\tilde O$ hides lower-order
terms. This is optimal up to the factor $\tilde O(\log(1/\e))$. The previous
best seed length was polylogarithmic in $m$ and $1/\e$.

Second we consider product tests $f\colon \zo^m \to \C_{\le 1}$. These
tests are the product of $k$ functions $f_i\colon \zo^n \to \C_{\le 1}$,
where the inputs of the $f_i$ are disjoint subsets of the $m$ variables and
$\C_{\le 1}$ is the complex unit disk. Here we obtain seed length $n \cdot
\poly \log (m/\e)$. This implies better generators for other classes of tests.
If moreover the $f_i$ have outputs independent of $n$ and $k$ (e.g.,
$\pmone$) then we obtain seed length $\tilde O(n + \log(k/\e)) \log(1/\e)$.
This is again optimal up to the factor $\tilde O(\log 1/\e)$, while the
previous best seed length was $\ge \sqrt k$.

A main component of our proofs is showing that these classes of tests are
fooled by almost $d$-wise independent distributions perturbed with noise.