Volume 13 (2017) Article 21 pp. 1-38
CCC 2016 Special Issue
Decoding Reed–Muller Codes over Product Sets
by
Revised: November 21, 2017
Published: December 31, 2017
[PDF (334K)]    [PS (2031K)]    [PS.GZ (419K)]
[Source ZIP]
Keywords: error-correcting codes, Reed--Muller codes, algebraic algorithms, Schwartz-Zippel lemma
ACM Classification: E.4, I.1.2
AMS Classification: 11T71, 94B35, 68W30

Abstract: [Plain Text Version]



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 $S^m$, for every $d < |S|$. Previously known algorithms could achieve this only if the set $S$ had some very special algebraic structure, or if the degree $d$ was significantly smaller than $|S|$. We also give a near-linear-time randomized algorithm, based on tools from list-decoding, to decode these codes from nearly half their minimum distance, provided $d < (1-\epsilon)|S|$ for constant $\epsilon > 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.

A conference version of this paper appeared in the Proceedings of the 31st Conference on Computational Complexity, 2016.