Decoding Reed-Muller codes over product sets

DOI10.4230/LIPICS.CCC.2016.11zbMATH Open1380.94148arXiv1511.07488MaRDI QIDQ5368745FDOQ5368745

Authors: John Y. Kim, Swastik Kopparty 

Publication date: 10 October 2017

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 $S^m$, 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 randomized algorithm, which is 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.

Full work available at URL: https://arxiv.org/abs/1511.07488

Recommendations

• Decoding Reed-Muller codes over product sets
• scientific article; zbMATH DE number 1594297
• List Decoding of&lt;tex&gt;$q$&lt;/tex&gt;-ary Reed–Muller Codes
• Efficiently decoding Reed-Muller codes from random errors
• Decoding of Reed Solomon codes beyond the error-correction bound

zbMATH Keywords

Reed-Muller codescoding theoryerror-correcting codespolynomial codes

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Linear codes (general theory) (94B05) Decoding (94B35)

Cited In (8)

• Local decoding and testing of polynomials over grids
• DECODING OF MATRIX-PRODUCT CODES
• Decoding multivariate multiplicity codes on product sets
• Noisy interpolating sets for low-degree polynomials
• Decoding Reed-Muller codes over product sets
• Stopping Set Analysis of Iterative Row-Column Decoding of Product Codes
• Decoding variants of Reed-Muller codes over finite grids
• Generalized Hamming weights of affine Cartesian codes

This page was built for publication: Decoding Reed-Muller codes over product sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5368745)