Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

The Sum of D Small-Bias Generators Fools Polynomials of Degree D

Emanuele ViolaContact Information

(1)  College of Computer and Information Science, Northeastern University, Boston, MA 02115, USA

Published online: 12 June 2009

Abstract.  We prove that the sum of d small-bias generators $$L : {\mathbb{F}}^{s} \rightarrow {\mathbb{F}}^{n}$$ fools degree-d polynomials in n variables over a field $${\mathbb{F}}$$, for any fixed degree d and field $${\mathbb{F}}$$, including $${\mathbb{F}} = {\mathbb{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 2d small-bias generators (as opposed to d in our result).

Keywords.  Polynomial - pseudorandom generator - small-bias - degree


Subject classification.  68Q99



Manuscript received 1 September 2008

Contact Information Emanuele Viola
Email: viola@ccs.neu.edu
Fulltext Preview (Small, Large)
Image of the first page of the fulltext


Export this article
Export this article as RIS | Text
 
Remote Address: 38.107.191.111 • Server: mpweb16
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)