ECCC-Report TR08-004https://eccc.weizmann.ac.il/report/2008/004Comments and Revisions published for TR08-004en-usFri, 18 Jan 2008 13:43:12 +0200
Paper TR08-004
| Noisy Interpolating Sets for Low Degree Polynomials |
Zeev Dvir,
Amir Shpilka
https://eccc.weizmann.ac.il/report/2008/004A Noisy Interpolating Set (NIS) for degree $d$ polynomials is a
set $S \subseteq \F^n$, where $\F$ is a finite field, such that
any degree $d$ polynomial $q \in \F[x_1,\ldots,x_n]$ can be
efficiently interpolated from its values on $S$, even if an
adversary corrupts a constant fraction of the values. In this
paper we construct explicit NIS for every prime field $\F_p$ and
any degree $d$. Our sets are of size $O(n^d)$ and have efficient
interpolation algorithms that can recover $q$ from a fraction
$\exp(-O(d))$ of errors.
Our construction is based on a theorem which roughly states that
if $S$ is a NIS for degree 1 polynomials then $d \cdot S= \{ a_1 +
\ldots + a_d \,|\, a_i \in S\}$ is a NIS for degree $d$
polynomials. Furthermore, given an efficient interpolation
algorithm for $S$, we show how to use it in a black-box manner to
build an efficient interpolation algorithm for $d \cdot S$.
As a corollary we get an explicit family of punctured Reed-Muller
codes that is a family of good codes that have an efficient
decoding algorithm from a constant fraction of errors. To the best
of our knowledge no such construction was known previously.
Fri, 18 Jan 2008 13:43:12 +0200https://eccc.weizmann.ac.il/report/2008/004