Emanuele Viola

We prove that the sum of $d$ small-bias generators $L

: \F^s \to \F^n$ fools degree-$d$ polynomials in $n$

variables over a prime field $\F$, for any fixed

degree $d$ and field $\F$, including $\F = \F_2 =

{0,1}$.

Our result improves on both the work by Bogdanov and

Viola ...
more >>>