Construction
The case corresponds to pseudorandom generators for linear functions and is solved by small-bias generators. For example, the construction of Naor & Naor (1990) achieves a seed length of, which is optimal up to constant factors.
Bogdanov & Viola (2007) conjectured that the sum of small-bias generators fools low-degree polynomials and were able to prove this under the Gowers inverse conjecture. Lovett (2009) proved unconditionally that the sum of small-bias spaces fools polynomials of degree . Viola (2008) proves that, in fact, taking the sum of only small-bias generators is sufficient to fool polynomials of degree . The analysis of Viola (2008) gives a seed length of .
Read more about this topic: Pseudorandom Generators For Polynomials
Famous quotes containing the word construction:
“Striving toward a goal puts a more pleasing construction on our advance toward death.”
—Mason Cooley (b. 1927)
“There’s no art
To find the mind’s construction in the face.”
—William Shakespeare (1564–1616)
“The construction of life is at present in the power of facts far more than convictions.”
—Walter Benjamin (1892–1940)