TY - GEN

T1 - Noisy Interpolating Sets for low degree polynomials

AU - Dvir, Zeev

AU - Shpilka, Amir

PY - 2008

Y1 - 2008

N2 - A Noisy Interpolating Set (NIS) for degree d polynomials is a set S ⊆ double-struck F signn, where F is a finite field, such that any degree d polynomial q ∈ F [x1,..., xn] 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 Fp 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.S = {a1 +... + ad | ai ∈ 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. 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.

AB - A Noisy Interpolating Set (NIS) for degree d polynomials is a set S ⊆ double-struck F signn, where F is a finite field, such that any degree d polynomial q ∈ F [x1,..., xn] 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 Fp 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.S = {a1 +... + ad | ai ∈ 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. 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.

UR - http://www.scopus.com/inward/record.url?scp=51749097357&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=51749097357&partnerID=8YFLogxK

U2 - 10.1109/CCC.2008.14

DO - 10.1109/CCC.2008.14

M3 - Conference contribution

AN - SCOPUS:51749097357

SN - 9780769531694

T3 - Proceedings of the Annual IEEE Conference on Computational Complexity

SP - 140

EP - 148

BT - Proceedings - 23rd Annual IEEE Conference on Computational Complexity, CCC 2008

T2 - 23rd Annual IEEE Conference on Computational Complexity, CCC 2008

Y2 - 23 June 2008 through 26 June 2008

ER -