logo

Video encyclopedia

Pseudorandom generators for polynomials

In theoretical computer science, a pseudorandom generator for low-degree polynomials is an efficient procedure that maps a short truly random seed to a longer pseudorandom string in such a way that low-degree polynomials cannot distinguish the output distribution of the generator from the truly random distribution. That is, evaluating any low-degree polynomial at a point determined by the pseudorandom string is statistically close to evaluating the same polynomial at a point that is chosen uniformly at random.

Relations