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 : https://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.