Zeev Dvir, Amir Shpilka

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

Shubhangi Saraf, Sergey Yekhanin

Let $f\in F_q[x]$ be a polynomial of degree $d\leq q/2.$ It is well-known that $f$ can be uniquely recovered from its values at some $2d$ points even after some small fraction of the values are corrupted. In this paper we establish a similar result for sparse polynomials. We show that ... more >>>