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:
“There’s no art
To find the mind’s construction in the face.”
—William Shakespeare (1564–1616)
“When the leaders choose to make themselves bidders at an auction of popularity, their talents, in the construction of the state, will be of no service. They will become flatterers instead of legislators; the instruments, not the guides, of the people.”
—Edmund Burke (1729–1797)
“The construction of life is at present in the power of facts far more than convictions.”
—Walter Benjamin (1892–1940)