  The multiplicity Schwartz-Zippel lemma bounds the total multiplicity of
zeroes of a multivariate polynomial on a product set. This lemma motivates the
multiplicity codes of Kopparty, Saraf and Yekhanin [J. ACM, 2014], who showed
how to use this lemma to construct high-rate locally-decodable codes. However,
the algorithmic results about these codes crucially rely on the fact that the
polynomials are evaluated on a vector space and not an arbitrary product set.
  In this work, we show how to decode multivariate multiplicity codes of large
multiplicities in polynomial time over finite product sets (over fields of
large characteristic and zero characteristic). Previously such decoding
algorithms were not known even for a positive fraction of errors. In contrast,
our work goes all the way to the distance of the code and in particular exceeds
both the unique decoding bound and the Johnson bound. For errors exceeding the
Johnson bound, even combinatorial list-decodablity of these codes was not
known.
  Our algorithm is an application of the classical polynomial method directly
to the multivariate setting. In particular, we do not rely on a reduction from
the multivariate to the univariate case as is typical of many of the existing
results on decoding codes based on multivariate polynomials. However, a vanilla
application of the polynomial method in the multivariate setting does not yield
a polynomial upper bound on the list size. We obtain a polynomial bound on the
list size by taking an alternative view of multivariate multiplicity codes. In
this view, we glue all the partial derivatives of the same order together using
a fresh set $z$ of variables. We then apply the polynomial method by viewing
this as a problem over the field $\mathbb{F}(z)$ of rational functions in $z$.
