pseudorandom generators for low degree polynomials
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.
pseudorandomness derandomization