2026-07-20T05:44:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5835 2024-03-06T10:37:09Z ddc:004 open_access

Decoding Reed-Muller Codes Over Product Sets Kim, John Y. Kopparty, Swastik polynomial codes Reed-Muller codes coding theory error-correcting codes 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 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-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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik John Y. Kim and Swastik Kopparty 2016 Is Part Of LIPIcs, Volume 50, 31st Conference on Computational Complexity (CCC 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2016.11 urn:nbn:de:0030-drops-58352 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2016.11 eng https://creativecommons.org/licenses/by/3.0/legalcode