The Sum of D Small-Bias Generators Fools Polynomials of Degree D

Abstract.

We prove that the sum of d small-bias generators $L : {\mathbb{F}}^{s} \rightarrow {\mathbb{F}}^{n}$ fools degree-d polynomials in n variables over a field ${\mathbb{F}}$, for any fixed degree d and field ${\mathbb{F}}$, including ${\mathbb{F}} = {\mathbb{F}}_{2} = \{0, 1\}$. Our result builds on, simplifies, and improves on both the work by Bogdanov and Viola (FOCS ’07) and the follow-up by Lovett (STOC ’08). The first relies on a conjecture that turned out to be true only for some degrees and fields, while the latter considers the sum of 2^d small-bias generators (as opposed to d in our result).