Noisy Interpolating Sets for low degree polynomials

Zeev Dvir, Amir Shpilka

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

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

Original languageEnglish (US)
Title of host publicationProceedings - 23rd Annual IEEE Conference on Computational Complexity, CCC 2008
Pages140-148
Number of pages9
DOIs
StatePublished - Sep 19 2008
Externally publishedYes
Event23rd Annual IEEE Conference on Computational Complexity, CCC 2008 - College Park, MD, United States
Duration: Jun 23 2008Jun 26 2008

Publication series

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

Other

Other23rd Annual IEEE Conference on Computational Complexity, CCC 2008
CountryUnited States
CityCollege Park, MD
Period6/23/086/26/08

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Noisy Interpolating Sets for low degree polynomials'. Together they form a unique fingerprint.

  • Cite this

    Dvir, Z., & Shpilka, A. (2008). Noisy Interpolating Sets for low degree polynomials. In Proceedings - 23rd Annual IEEE Conference on Computational Complexity, CCC 2008 (pp. 140-148). [4558818] (Proceedings of the Annual IEEE Conference on Computational Complexity). https://doi.org/10.1109/CCC.2008.14