Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR07-132 | 8th December 2007 00:00

The sum of d small-bias generators fools polynomials of degree d

RSS-Feed




TR07-132
Authors: Emanuele Viola
Publication: 16th December 2007 05:01
Downloads: 3671
Keywords: 


Abstract:

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 (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.



ISSN 1433-8092 | Imprint