Noisy interpolation of sparse polynomials, and applications

Shubhangi Saraf, MIT
Fine Hall 224

Let f in $F_q[x]$ be a polynomial of degree $d < 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 talk we will establish a similar result for sparse polynomials. We show that a k-sparse polynomial $f$ in $F_q[x]$ of degree $d < q/2$ can be recovered from its values at O(k) randomly chosen points, even if a small fraction of the values of f are adversarially corrupted. Our proof relies on an iterative technique for analyzing the rank of a random minor of a matrix. We use the same technique to establish a collection of other results on locally decodable codes and rigid matrices. Based on joint work with Sergey Yekhanin.