THE SUM OF D SMALL-BIAS GENERATORS FOOLS POLYNOMIALS OF DEGREE D

摘要

We prove that the sum of d small-bias generators L : F~s → F~n fools degree-d polynomials in n variables over a field F, for any fixed degree d and field F, including F = 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).