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

Eli Ben-Sasson, Dan Carmon, Swastik Kopparty, David Levit

Over finite fields $F_q$ containing a root of unity of smooth order $n$ (smoothness means $n$ is the product of small primes), the Fast Fourier Transform (FFT) leads to the fastest known algebraic algorithms for many basic polynomial operations, such as multiplication, division, interpolation and multi-point evaluation. These operations can ... more >>>