Decoding Reed-Muller Codes Over Product Sets
John Y. Kim, Swastik Kopparty · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2016
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 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.