Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR09-088 | 29th September 2009 11:37

Explicit lower bound for fooling polynomials by the sum of small-bias generators

RSS-Feed




TR09-088
Authors: Shachar Lovett, Yoav Tzur
Publication: 2nd October 2009 23:19
Downloads: 4092
Keywords: 


Abstract:

Recently, Viola (CCC'08) showed that the sum of $d$ small-biased distributions fools degree-$d$ polynomial tests; that is, every polynomial expression of degree at most $d$ in the bits of the sum has distribution very close to that induced by this expression evaluated on uniformly selected random bits. We show that this is tight by showing an explicit construction of a small-bias generator (with exponentially small bias), and an explicit degree $d+1$ polynomial, that is distributed almost uniformly on random input, but always takes the value zero when evaluated on the sum of $d$ independent copies of this generator.



ISSN 1433-8092 | Imprint