Noisy Interpolation of Sparse Polynomials, and Applications

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 paper we establish a similar result for sparse polynomials. We show that a k-sparse polynomial f 2 Fq[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. Specifically,_ We show that restricting any linear [n; k; _n]q code to a randomly chosen set of O(k) coordinates with highprobability yields an asymptotically good code. _ We improve the state of the art in locally decodable codes,showing that similarly to Reed Muller codes matching vector codes require only a constant increase in querycomplexity in order to tolerate a constant fraction of errors. This result yields a moderate reduction in thequery complexity of the currently best known codes. _ We improve the state of the art in constructions of explicit rigid matrices. For any prime power q and integers n and d we construct an explicit matrix M with exp(d) _ n rows and n columns such that the rank of M stays above n=2 even if every row of M is arbitrarily altered in up to d coordinates. Earlier, such constructions were available only for q = O(1) or q = (n)