Theory of Computing
-------------------
Title     : Decoding Reed–Muller Codes over Product Sets
Authors   : John Y. Kim and Swastik Kopparty
Volume    : 13
Number    : 21
Pages     : 1-38
URL       : https://theoryofcomputing.org/articles/v013a021

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 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.