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       : https://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.