ECCC-Report TR13-155https://eccc.weizmann.ac.il/report/2013/155Comments and Revisions published for TR13-155en-usWed, 12 Mar 2014 07:53:20 +0200
Revision 2
| Pseudorandom Generators for Low Degree Polynomials from Algebraic Geometry Codes |
Gil Cohen,
Amnon Ta-Shma
https://eccc.weizmann.ac.il/report/2013/155#revision2Constructing 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.
Wed, 12 Mar 2014 07:53:20 +0200https://eccc.weizmann.ac.il/report/2013/155#revision2
Revision 1
| Pseudorandom Generators for Low Degree Polynomials from Algebraic Geometry Codes |
Gil Cohen,
Amnon Ta-Shma
https://eccc.weizmann.ac.il/report/2013/155#revision1Constructing 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.Tue, 19 Nov 2013 13:35:36 +0200https://eccc.weizmann.ac.il/report/2013/155#revision1
Paper TR13-155
| Pseudorandom Generators for Low Degree Polynomials from Algebraic Geometry Codes |
Gil Cohen,
Amnon Ta-Shma
https://eccc.weizmann.ac.il/report/2013/155Constructing 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.Sun, 10 Nov 2013 18:19:59 +0200https://eccc.weizmann.ac.il/report/2013/155