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.
|
 |
The Sum of D Small-Bias Generators Fools Polynomials of Degree D
| |
|
The Sum of D Small-Bias Generators Fools Polynomials of Degree D
Emanuele Viola1 
| (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  fools degree- d polynomials in n variables over a field  , for any fixed degree d and field  , including  . 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 2 d 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
Fulltext Preview (Small, Large)
|
|
|
|
|
|