Pseudorandom Generators for Low Degree Polynomials from Algebraic Geometry Codes

摘要

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(dlogn+d2d), and thus this construction yields a non-trivial result only for d=O(logn). Bogdanov [STOC 2005] presented a pseudorandom generator with seed length O(d4logn). However, it is promised to work only for fields of size (d10log2n).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 (d12) and has seed length O(d4logn). The running time of our construction is nO(d4). 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 nO(1). We also make a first step at affirming the conjecture.