Volume 7 (2011) Article 1 pp. 1-18
Noisy Interpolating Sets for Low-Degree Polynomials
by
Published: February 12, 2011
[PDF (251K)]    [PS (957K)]    [PS.GZ (269K)]
[Source ZIP]
Keywords: polynomial interpolation, error-correcting codes
ACM Classification: F.2.2
AMS Classification: 68P30, 68Q25

Abstract: [Plain Text Version]

$\newcommand{\F}{{\mathbb F}}$ A 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 obtain an explicit family of punctured Reed-Muller codes (codes that are restrictions of a Reed-Muller code to a subset of the coordinates) which are good codes and have an efficient decoding algorithm against a constant fraction of errors. To the best of our knowledge, even the existence of punctured Reed-Muller codes that are good codes was not previously known.