Constructing pseudorandom generators for low degree polynomials has received a considerable attention in the past decade. Viola [CC 2009], following an exciting line of research, constructed a
pseudorandom generator for degree $d$ polynomials in $n$ variables, over any prime field. The seed length used is $O(d \log{n} + d 2^d)$, and thus this construction yields a non-trivial result only for $d = O(\log{n})$. Bogdanov [STOC 2005] presented a pseudorandom generator with seed length $O(d^4 \log{n})$. However, it is promised to work only for fields of size $\Omega(d^{10} \log^{2} n})$. The work of Lu [CCC 2012], combined with that of Bogdanov, yields a pseudorandom generator with seed length $O(d^4 \log{n})$ for fields of size $\Omega(d^{6+c})$ -- independent of $n$, where $c$ is an arbitrarily small constant. Based on these works, Guruswami and Xing [CCC 2014] devised a construction with a similar seed length for fields of size $O(d^6)$.

In this work we show that for any $d$, a random sub-code (with a proper dimension) of any good algebraic geometry code, is a hitting set for degree $d$ polynomials. By derandomizing this assertion, together with the work of Bogdanov, we obtain a construction of a pseudorandom generator for degree $d$ polynomials over fields of size $O(d^{12})$, and seed length $O(d^4 \log{n})$. The running-time of our construction is $n^{\poly(d)}$. However, the running-time can be improved to $\poly(n,d)$ assuming Riemann-Roch spaces of certain algebraic function fields are, in some sense, strongly explicit. We believe this open problem is interesting on its own, and take a first step at affirming the conjecture.

Although quantitatively our result does not match the parameters of Guruswami and Xing, our construction is clean mathematically and conceptually simpler. We consider the proof technique to be the main contribution of this paper, and believe it will find other applications in complexity theory. In the heart of our proofs is a reduction from the problem of assuring independence between monomials to the much simpler problem of avoiding collisions over the integers. Our reduction heavily relies on the Riemann-Roch theorem.

Constructing pseudorandom generators for low degree polynomials has received a considerable attention in the past decade. Viola [CC 2009], following an exciting line of research, constructed a pseudorandom generator for degree d polynomials in n variables, over any prime field. The seed length used is $O(d \log{n} + d 2^d)$, and thus this construction yields a non-trivial result only for $d = O(\log{n})$. Bogdanov [STOC 2005] presented a pseudorandom generator with seed length $O(d^4 \log{n})$. However, it is promised to work only for fields of size $\Omega(d^{10} \log^{2}{n})$.

The main result of this paper is a construction of a pseudorandom generator for low degree polynomials based on algebraic geometry codes. Our pseudorandom generator works for fields of size $\Omega(d^{12})$ and has seed length $O(d^4 \log{n})$. The running time of our construction is $n^{O(d^4)}$. We postulate a conjecture concerning the explicitness of a certain Riemann-Roch space in function fields. If true, the running time of our pseudorandom generator would be reduced to $n^{O(1)}$. We also make a first step at affirming the conjecture.

There was a miscalculation in the claimed field size. It is O(d^12) and not O(d^6) as stated in the original version. In the second construction, the exponent in d is not 8 as claimed, but 20.

Constructing pseudorandom generators for low degree polynomials has received a considerable attention in the past decade. Viola [CC 2009], following an exciting line of research, constructed a pseudorandom generator for degree d polynomials in n variables, over any prime field. The seed length used is $O(d \log{n} + d 2^d)$, and thus this construction yields a non-trivial result only for $d = O(\log{n})$. Bogdanov [STOC 2005] presented a pseudorandom generator with seed length $O(d^4 \log{n})$. However, it is promised to work only for fields of size $\Omega(d^{10} \log^{2}{n})$.

The main result of this paper is a construction of a pseudorandom generator for low degree polynomials based on algebraic geometry codes. Our pseudorandom generator works for fields of size $\Omega(d^6)$ and has seed length $O(d^4 \log{n})$. The running time of our construction is $n^{O(d^4)}$. We postulate a conjecture concerning the explicitness of a certain Riemann-Roch space in function fields. If true, the running time of our pseudorandom generator would be reduced to n^{O(1)}$. We also make a first step at affirming the conjecture.