文章基本信息

标题：List-Decoding Multiplicity Codes
本地全文：下载
作者：Swastik Kopparty
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2012
卷号：2012
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We study the list-decodability of multiplicity codes. These codes, which are based on evaluations of high-degree polynomials and their derivatives, have rate approaching 1 while simultaneously allowing for sublinear-time error-correction. In this paper, we show that multiplicity codes also admit powerful list-decoding and local list-decoding algorithms correcting a large fraction of errors. Stated simply, we give algorithms for recovering a polynomial given several evaluations of it and its derivatives, where possibly many of the given evaluations are incorrect. Our first main result shows that univariate multiplicity codes over prime fields can be list-decoded upto the so called ``list-decoding capacity". Specifically, we show that univariate multiplicity codes of rate R over prime fields can be list-decoded from (1−R−)-fraction errors in polynomial time. This resembles the behavior of the Folded Reed-Solomon Codes of Guruswami and Rudra. The list-decoding algorithm is based on constructing a differential equation of which the desired codeword is a solution; this differential equation is then solved using a power-series approach (a variation of Hensel lifting) along with other algebraic ideas. Our second main result is a list-decoding algorithm for decoding multivariate multiplicity codes upto their Johnson radius. The key ingredient of this algorithm is the construction of a special family of ``algebraically-repelling" curves passing through the points of Fqm; no moderate-degree multivariate polynomial over Fqm can simultaneously vanish on all these curves. These curves enable us to reduce the decoding of multivariate multiplicity codes over Fqm to several instances of decoding univariate multiplicity codes over the big field Fqm, for which such list-decoding algorithms are known.
关键词：Differential Equations, Error-correcting codes, finite fields, list-decoding, Locally decodable codes, multiplicity codes, polynomials, Sublinear-time algorithms