ECCC-Report TR07-132https://eccc.weizmann.ac.il/report/2007/132Comments and Revisions published for TR07-132en-usSun, 16 Dec 2007 05:01:23 +0200
Paper TR07-132
| The sum of d small-bias generators fools polynomials of degree d |
Emanuele Viola
https://eccc.weizmann.ac.il/report/2007/132We 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 (FOCS '07) and the beautiful follow-up by Lovett
(ECCC '07). 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).
Our proof builds on and somewhat simplifies the
arguments by Bogdanov and Viola (FOCS '07) and by
Lovett (ECCC '07). Its core is a case analysis based
on the \emph{bias} of the polynomial to be fooled.
Sun, 16 Dec 2007 05:01:23 +0200https://eccc.weizmann.ac.il/report/2007/132