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 Sm, for every d   0.#R##N##R##N#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.
['John Y. Kim', 'Swastik Kopparty']
Decoding Reed-Muller codes over product sets