Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR11-044 | 25th March 2011 22:45

Noisy Interpolation of Sparse Polynomials, and Applications


Authors: Shubhangi Saraf, Sergey Yekhanin
Publication: 26th March 2011 08:10
Downloads: 2981


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 a $k$-sparse polynomial $f\in F_q[x]$ of degree $d\leq 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,\delta n]_q$ code to a randomly chosen set of $O(k)$ coordinates with high probability 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 query complexity in order to tolerate a constant fraction of errors. This result yields a moderate reduction in the query 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)\cdot 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=\Omega(n).$

ISSN 1433-8092 | Imprint