Pseudorandom generators for low degree polynomials
Andrej Bogdanov · 2005
We investigate constructions of pseudorandom generators that fool polynomial tests of degree d in m variables over finite fields F. Our main construction gives a generator with seed length O(d 4 log m(1 + log(d/ɛ) / log log m) + log |F|) bits that achieves arbitrarily small bias ɛ and works whenever |F | is at least polynomial in d, log m, and 1/ɛ. We also present an alternate construction that uses a seed that can be described by O(c 2 d 8 m 6/(c−2) log(d/ɛ) + log |F|) bits (more precisely, O(c 2 d 8 m 6/(c−2) ) field elements, each chosen from a set of size poly(cd/ɛ), plus two field elements ranging over all of F), works whenever |F | is at least polynomial in c, d, and 1/ɛ, and has the property that every element of the output is a function of at most c field elements in the input. Both generators are computable by small arithmetic circuits. The main tool used in the construction is a reduction that allows us to transform any “dense ” hitting set generator for polynomials into a pseudorandom generator. 1