Pseudorandom generators for polynomials
Encyclopedia
In theoretical computer science
a pseudorandom generator for low-degree polynomials is an efficiently computable function whose output is indistinguishable from the uniform distribution by evaluation of low-degree polynomials in the following sense.
for polynomials of degree 
over a Finite field
F is an efficient procedure that stretches
field elements into 
field elements and fools any
polynomial of degree d in n variables over F: For every such polynomial p, the statistical distance between the distributions
, for uniform 
in 
, and 
, for uniform 
in 
, is at most a small 
.
which give constructions with seed length
(this is optimal up to constant factors). Following the sequence of papers (http://www.ccs.neu.edu/home/viola/papers/gen.pdf, http://shachar.lovett.googlepages.com/prg_poly.pdf) it was established in http://www.ccs.neu.edu/home/viola/papers/d.pdf that a sum of 
small-bias spaces fools degree 
polynomials. This gives a construction with seed length 
.
Theoretical computer science
Theoretical computer science is a division or subset of general computer science and mathematics which focuses on more abstract or mathematical aspects of computing....
a pseudorandom generator for low-degree polynomials is an efficiently computable function whose output is indistinguishable from the uniform distribution by evaluation of low-degree polynomials in the following sense.
Definition
A pseudorandom generator for polynomials of degree over a Finite fieldFinite field
In abstract algebra, a finite field or Galois field is a field that contains a finite number of elements. Finite fields are important in number theory, algebraic geometry, Galois theory, cryptography, and coding theory...
F is an efficient procedure that stretches
field elements into field elements and fools anypolynomial of degree d in n variables over F: For every such polynomial p, the statistical distance between the distributions
, for uniform in , and , for uniform in , is at most a small .Construction
The case of linear polynomials is solved by small-bias spacesEpsilon-Biased Sample Spaces
In computer science \epsilon-biased sample spaces, also known as \epsilon-biased generators or small-bias probability spaces, refer to small probability spaces that approximate larger spaces as defined below...
which give constructions with seed length
(this is optimal up to constant factors). Following the sequence of papers (http://www.ccs.neu.edu/home/viola/papers/gen.pdf, http://shachar.lovett.googlepages.com/prg_poly.pdf) it was established in http://www.ccs.neu.edu/home/viola/papers/d.pdf that a sum of small-bias spaces fools degree polynomials. This gives a construction with seed length .