ECCC-Report TR13-175https://eccc.weizmann.ac.il/report/2013/175Comments and Revisions published for TR13-175en-usTue, 06 May 2014 04:05:06 +0300
Revision 1
| Hitting Sets for Low-Degree Polynomials with Optimal Density |
Venkatesan Guruswami,
Chaoping Xing
https://eccc.weizmann.ac.il/report/2013/175#revision1We give a length-efficient puncturing of Reed-Muller codes which preserves its distance properties. Formally, for the Reed-Muller code encoding $n$-variate degree-$d$ polynomials over ${\mathbb F}_q$ with $q \ge \Omega(d/\delta)$, we present an explicit (multi)-set $S \subseteq {\mathbb F}_q^n$ of size $N=\mathrm{poly}(n^d/\delta)$ such that every nonzero polynomial vanishes on at most $\delta N$ points in $S$. Equivalently, we give an explicit hitting set generator (HSG) for degree-$d$ polynomials of seed length $\log N = O(d \log n + \log (1/\delta))$ with ``density" $1-\delta$ (meaning every nonzero polynomial is nonzero with probability at least $1-\delta$ on the output of the HSG). The seed length is optimal up to constant factors, as is the required field size $\Omega(d/\delta)$.
Plugging our HSG into a construction of Bogdanov (STOC'05) gives explicit pseudorandom generators for $n$-variate degree-$d$ polynomials with error $\epsilon$ and seed length $O(d^4 \log n + \log (1/\epsilon))$ whenever the field size satisfies $q \ge \Omega(d^6/\epsilon^2)$.
Our approach involves concatenating previously known HSGs over large fields with multiplication friendly codes based on algebraic curves. This allows us to bring down the field size to the optimal bounds. Such multiplication friendly codes, which were first introduced to study the bilinear complexity of multiplication in extension fields, have since found other applications, and in this work we give a new use of this notion in algebraic pseudorandomness.
Tue, 06 May 2014 04:05:06 +0300https://eccc.weizmann.ac.il/report/2013/175#revision1
Paper TR13-175
| Hitting Sets for Low-Degree Polynomials with Optimal Density |
Venkatesan Guruswami,
Chaoping Xing
https://eccc.weizmann.ac.il/report/2013/175We give a length-efficient puncturing of Reed-Muller codes which preserves its distance properties. Formally, for the Reed-Muller code encoding $n$-variate degree-$d$ polynomials over ${\mathbb F}_q$ with $q \ge \Omega(d/\delta)$, we present an explicit (multi)-set $S \subseteq {\mathbb F}_q^n$ of size $N=\mathrm{poly}(n^d/\delta)$ such that every nonzero polynomial vanishes on at most $\delta N$ points in $S$. Equivalently, we give an explicit hitting set generator (HSG) for degree-$d$ polynomials of seed length $\log N = O(d \log n + \log (1/\delta))$ with ``density" $1-\delta$ (meaning every nonzero polynomial is nonzero with probability at least $1-\delta$ on the output of the HSG). The seed length is optimal up to constant factors, as is the required field size $\Omega(d/\delta)$.
Plugging our HSG into a construction of Bogdanov (STOC'05) gives explicit pseudorandom generators for $n$-variate degree-$d$ polynomials with error $\epsilon$ and seed length $O(d^4 \log n + \log (1/\epsilon))$ whenever the field size satisfies $q \ge \Omega(d^6/\epsilon^2)$.
Our approach involves concatenating previously known HSGs over large fields with multiplication friendly codes based on algebraic curves. This allows us to bring down the field size to the optimal bounds. Such multiplication friendly codes, which were first introduced to study the bilinear complexity of multiplication in extension fields, have since found other applications, and in this work we give a new use of this notion in algebraic pseudorandomness.
Fri, 06 Dec 2013 19:42:47 +0200https://eccc.weizmann.ac.il/report/2013/175