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:
“No real “vital” character in fiction is altogether a conscious construction of the author. On the contrary, it may be a sort of parasitic growth upon the author’s personality, developing by internal necessity as much as by external addition.”
—T.S. (Thomas Stearns)
“There’s no art
To find the mind’s construction in the face:
He was a gentleman on whom I built
An absolute trust.”
—William Shakespeare (1564–1616)
“No construction stiff working overtime takes more stress and straining than we did just to stay high.”
—Gus Van Sant, U.S. screenwriter and director, and Dan Yost. Bob Hughes (Matt Dillon)