Name
Abstract | ||
|---|---|---|
We give a polynomial time algorithm to decode multivariate polynomial codes of degree d up to half their minimum distance, when the evaluation points are an arbitrary product set Sm, for every d < |S|. Previously known algorithms can achieve this only if the set S has some very special algebraic structure, or if the degree d is significantly smaller than |S|. We also give a near-linear time algorithm, which is based on tools from list-decoding, to decode these codes from nearly half their minimum distance, provided d < (1 - ε)|S| for constant ε > 0. Our result gives an m-dimensional generalization of the well known decoding algorithms for Reed-Solomon codes, and can be viewed as giving an algorithmic version of the Schwartz-Zippel lemma. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.4230/LIPIcs.CCC.2016.11 | conference on computational complexity |
Keywords | Field | DocType |
polynomial codes,Reed-Muller codes,coding theory,error-correcting codes | Discrete mathematics,Combinatorics,Berlekamp–Welch algorithm,Sequential decoding,Block code,Expander code,Reed–Solomon error correction,Reed–Muller code,Linear code,List decoding,Mathematics | Journal |
Volume | Issue | ISSN |
13 | 1 | 1868-8969 |
Citations | PageRank | References |
2 | 0.44 | 6 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| John Y. Kim | 1 | 2 | 1.12 |
| Swastik Kopparty | 2 | 384 | 32.89 |