### Abstract

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

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 | 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

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

## Cite this

*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