Pseudorandom Generators For Polynomials - Construction

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)

    Striving toward a goal puts a more pleasing construction on our advance toward death.
    Mason Cooley (b. 1927)

    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)