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 O ( log ( m \e )) log (1 \e ) , where O hides lower-order terms. This is optimal up to the factor O ( log (1 \e )) . The previous best seed length was polylogarithmic in m and 1 \e .

Second we consider product tests f : \zo m \C 1 . These tests are the product of k functions f i : \zo n \C 1 , where the inputs of the f i are disjoint subsets of the m variables and \C 1 is the complex unit disk. Here we obtain seed length n \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 O ( n + log ( k \e )) log (1 \e ) . This is again optimal up to the factor O ( log 1 \e ) , while the previous best seed length was 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.