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:

    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 is, I think, no point in the philosophy of progressive education which is sounder than its emphasis upon the importance of the participation of the learner in the formation of the purposes which direct his activities in the learning process, just as there is no defect in traditional education greater than its failure to secure the active cooperation of the pupil in construction of the purposes involved in his studying.
    John Dewey (1859–1952)

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