ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > KEYWORD > INTERPOLATION:
Reports tagged with interpolation:
TR08-004 | 2nd January 2008
Zeev Dvir, Amir Shpilka

Noisy Interpolating Sets for Low Degree Polynomials

A Noisy Interpolating Set (NIS) for degree $d$ polynomials is a set $S \subseteq \F^n$, where $\F$ is a finite field, such that any degree $d$ polynomial $q \in \F[x_1,\ldots,x_n]$ can be efficiently interpolated from its values on $S$, even if an adversary corrupts a constant fraction of the values. ... more >>>



ISSN 1433-8092 | Imprint