Noisy Interpolating Sets for low degree polynomials

Zeev Dvir; Amir Shpilka

doi:10.1109/CCC.2008.14

Noisy Interpolating Sets for low degree polynomials

Zeev Dvir, Amir Shpilka

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

2 Scopus citations

Abstract

A Noisy Interpolating Set (NIS) for degree d polynomials is a set S ⊆ double-struck F signⁿ, where F is a finite field, such that any degree d polynomial q ∈ F [x₁,..., 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.S = {a₁ +... + a_d

Original language	English (US)
Title of host publication	Proceedings - 23rd Annual IEEE Conference on Computational Complexity, CCC 2008
Pages	140-148
Number of pages	9
DOIs	https://doi.org/10.1109/CCC.2008.14
State	Published - Sep 19 2008
Externally published	Yes
Event	23rd Annual IEEE Conference on Computational Complexity, CCC 2008 - College Park, MD, United States Duration: Jun 23 2008 → Jun 26 2008

Publication series

Name	Proceedings of the Annual IEEE Conference on Computational Complexity
ISSN (Print)	1093-0159

Other

Other	23rd Annual IEEE Conference on Computational Complexity, CCC 2008
Country/Territory	United States
City	College Park, MD
Period	6/23/08 → 6/26/08

All Science Journal Classification (ASJC) codes

Software
Theoretical Computer Science
Computational Mathematics

Access to Document

10.1109/CCC.2008.14

Cite this

@inproceedings{096da32fb00645fcab6c399137a25dad,

title = "Noisy Interpolating Sets for low degree polynomials",

abstract = "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",

author = "Zeev Dvir and Amir Shpilka",

year = "2008",

month = sep,

day = "19",

doi = "10.1109/CCC.2008.14",

language = "English (US)",

isbn = "9780769531694",

series = "Proceedings of the Annual IEEE Conference on Computational Complexity",

pages = "140--148",

booktitle = "Proceedings - 23rd Annual IEEE Conference on Computational Complexity, CCC 2008",

note = "23rd Annual IEEE Conference on Computational Complexity, CCC 2008 ; Conference date: 23-06-2008 Through 26-06-2008",

}

Dvir, Z & Shpilka, A 2008, Noisy Interpolating Sets for low degree polynomials. in Proceedings - 23rd Annual IEEE Conference on Computational Complexity, CCC 2008., 4558818, Proceedings of the Annual IEEE Conference on Computational Complexity, pp. 140-148, 23rd Annual IEEE Conference on Computational Complexity, CCC 2008, College Park, MD, United States, 6/23/08. https://doi.org/10.1109/CCC.2008.14

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 -

Noisy Interpolating Sets for low degree polynomials

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this