Theory of Computing ------------------- Title : More on Bounded Independence Plus Noise: Pseudorandom Generators for Read-Once Polynomials Authors : Chin Ho Lee and Emanuele Viola Volume : 16 Number : 7 Pages : 1-50 URL : http://www.theoryofcomputing.org/articles/v016a007 Abstract -------- $\newcommand{\C}{{\mathbb C}} \newcommand{\zo}{\{0,1\}} \def\eps{\varepsilon} \def\Blocklength{\ell} \def\poly{\mathrm{poly}} \def\polylog{\mathrm{polylog}}$ 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 $\eps$ we obtain seed length $\tilde O(\log(m/\eps)\log(1/\eps))$. This is optimal up to a factor of $\log(1/\eps)\cdot\poly\log\log(m/\eps)$. The previous best seed length was polylogarithmic in $m$ and $1/\eps$. Second, we consider product tests $f: {0,1}^m\to\C_{\le 1}$. These tests are the product of $k$ functions $f_i: {0,1}^\ell \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 $\ell\cdot\polylog (m/\eps)$. This implies better generators for other classes of tests. If moreover the $f_i$ have output range $\{-1,0,1\}$ then we obtain seed length $\tilde O((\log(k/\eps)+\ell)(\log(1/\eps)+\log\log m))$. This is again optimal up to a factor of $\log(1/\eps)\cdot\polylog(\ell,\log k,\log m,\log(1/\eps))$, 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.