期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2011
卷号：2011
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：Fq[x] be a polynomial of degree dq2 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 fFq[x] of degree dq2 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 [nkn]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)n rows and n columns such that the rank of M stays above n2 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)
