ECCC-Report TR09-088https://eccc.weizmann.ac.il/report/2009/088Comments and Revisions published for TR09-088en-usFri, 02 Oct 2009 23:19:08 +0200
Paper TR09-088
| Explicit lower bound for fooling polynomials by the sum of small-bias generators |
Shachar Lovett,
Yoav Tzur
https://eccc.weizmann.ac.il/report/2009/088Recently, 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.Fri, 02 Oct 2009 23:19:08 +0200https://eccc.weizmann.ac.il/report/2009/088