TY - GEN
T1 - Noisy Interpolating Sets for low degree polynomials
AU - Dvir, Zeev
AU - Shpilka, Amir
PY - 2008/9/19
Y1 - 2008/9/19
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
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
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 -