Theory of Computing
-------------------
Title : Noisy Interpolating Sets for Low-Degree Polynomials
Authors : Zeev Dvir and Amir Shpilka
Volume : 7
Number : 1
Pages : 1-18
URL : http://www.theoryofcomputing.org/articles/v007a001
Abstract
--------
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,...,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
dS= { a_1 + ... + 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 dS.
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.