The Sum of D Small-Bias Generators Fools Polynomials of Degree D
Emanuele Viola · Computational Complexity · 2008
We prove that the sum of d small-bias generators L : Fsrarr Fnfools degree-d polynomials in n variables over a prime field F, for any fixed degree d and field F, including F = F2= {0,1}. Our result improves on both the work by Bogdanov and Viola (FOCS '07) and the beautiful 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 of2d small-bias generators (as opposed to d in our result). Our proof builds on and somewhat simplifies the arguments by Bogdanov and Viola (FOCS '07) and by Lovett (STOC '08). Its core is a case analysis based on the bias of the polynomial to befooled.