_{\ba, j}(\vecY)$ are $P^{(\ii)}(\ba)$, for $\ii$ satisfying $\wt(\ii) = j$. 
Thus $P^{(\ii)}(\ba) = 0$ for each $\ba$ and each $\ii$ with $\wt(\ii) < s$.

Therefore $\mult(P, \ba) \geq s$ for each $\ba \in \F_q^m$, which
implies that $P = 0$, as desired.
\end{proofof}


\subsection{Local List-Decoding}

The list-decoding algorithm for multivariate multiplicity codes
from the Johnson radius can be used to give a
{\em local list-decoding} algorithm for multivariate multiplicity
codes upto the Johnson radius. Since the definition of local
list-decoding is somewhat involved, we refer the reader to
the appendix of~\cite{K} for the algorithm and its analysis.











\section{Encoding}
\label{sec:encoding}

In this section we discuss encoding algorithms.

Since multiplicity codes are $\F_q$-linear subspaces
of $\Sigma^{\F_q^m}$, it is natural to choose an encoding map
which is $\F_q$-linear. One very natural encoding map to consider
is the map:
$$ E: \F_q^{d + m \choose m } \to \mathcal C,$$
which treats its input as a vector of coefficients of
monomials for a polynomial $P \in \F_q[\vecX]$ of degree at most $d$,
and outputs $\Enc_{s,d,m,q}(P)$. It is well known that the
task of computing $E$, namely evaluating a given polynomial
and all its derivatives of order at most $s$ at all points of $\F_q^m$
can be performed in near-linear time $O( (d^m + q^m) \cdot {m+s \choose m} \cdot \log(d^m + q^m))$.

However, for the purposes of local decoding, it will be important
to choose the encoding map $E: \Sigma_0^k \to \mathcal C \subseteq \Sigma^n$
a bit more carefully. The goal
is to have the encoding be {\em systematic}; i.e., to have the 
symbols of the message appear as symbols (or parts of symbols) 
of its encoding. Once we have such an encoding map, a local correction
algorithm immediately gives us a local decoding algorithm.

Such a systematic encoding map can be chosen by giving an 
{\em interpolating set}. Concretely, for a given $s, d, m, q$, we
want a set $S \subseteq \F_q^m \times \{ \ii \mid \wt(\ii) < s\}$
such that for every $f: S \rightarrow \F_q$, there is {\bf exactly one} $P(X_1, \ldots, X_m) \in \F_q[X_1, \ldots, X_m]$
of degree at most $d$ such that for each $(\ba, \ii) \in S$, $P^{(\ii)}(\ba) = f(\ba, \ii)$.

It is easy to see that such sets $S$ exist,
and any such set $S$ must have $|S| = {d + m \choose m}$. 
In order for the so obtained local decoding algorithm to
run in sublinear time (assuming the local correction algorithm runs
in sublinear time), it will be important that this interpolating
set be {\em explicit}: given message coordinate $i \in  [k]$, we should
be able to compute, in time $\poly(\log(k))$,
the codeword coordinate $j \in [n]$ which contains the $i$th symbol
of the codeword.
In~\cite{K}, an explicit such interpolating set was given.

 

\begin{theorem}[\cite{K}]
\label{thm:interp}
There exist explicit interpolating sets $S$ as above.

Thus there exist explicit systematic encoding maps for
multiplicity codes.
\end{theorem}

The interpolating sets for multiplicity codes constructed 
above are in fact simple combinations of interpolating sets
for Reed-Muller codes. Furthermore, 
it is known that there exist interpolating sets for Reed-Muller
codes from which polynomial interpolation can be performed in near-linear time.
This implies, by inspecting the proof of Theorem~\ref{thm:interp},
that the encoding map described above can be computed in near-linear time.


\section{Discussion}

\begin{enumerate}

\item The improved local decoding algorithm given in Section~\ref{sec:local}
had two main ideas over the original local decoding algorithm of~\cite{KSY}:
getting more information from each line, and robustly combining this information
across different lines by decoding a multiplicity code.

The first idea is naturally motivated by an incongruity between the three papers: \cite{KSY} (on local correction of multiplicity codes), \cite{GKS} (on affine invariant codes, local correction of affine invariant codes, and their relationship to bounds on Nikodym sets), and \cite{DKSS} (giving lower bounds on the size of Nikodym sets via the extended method of multiplicities).

A Nikodym set is a set $N \subseteq \F_q^m$ such that for every
$\ba \in \F_q^m$, there is some line $L \subseteq \F_q^m$ passing through
$\ba$, such that $L \setminus \{\ba\} \subseteq N$ (i.e., the entire
line, except possibly $\ba$, is contained in $N$).
In~\cite{GKS} it was noted that lower bounds on Nikodym sets 
follow from the existence of algebraic error-correcting codes that
can be locally corrected at $\ba \in \F_q^m$ by querying a line through
$\ba$. In~\cite{DKSS}, the extended method of multiplicities (which in
retrospect can be interpreted in the language of multiplicity codes)
was used to show a lower bound of $\left(\frac{q}{2}\right)^m$ on the
size of Nikodym sets. On the other hand, if one tried to use the original local
correction algorithm of~\cite{KSY} for multiplicity codes
to prove a lower bound on Nikodym sets (via the~\cite{GKS} connection),
we would get a significantly weaker bound than the bound of~\cite{DKSS}.
All this suggests that there should be a better algorithm for local
correction of multiplicity codes, and (looking at the details) a way to get more
information from each line.

The second idea is motivated by a different incongruity: the local correction
algorithm of~\cite{KSY} combines information from different lines
by decoding a Reed-Muller code, but there
seems to be no reason for the $s = 1$ case of multiplicity codes
(i.e., Reed-Muller codes) to
receive preferential treatment amongst all possibilities for $s$.
The new algorithm resolves this incongruity, and lets us use
fewer lines for the local decoding.


\item The decoding algorithm described in Section~\ref{sec:var} based on
$m$ linearly independent lines was motivated by another problem in the combinatorial
geometry: the joints problem~\cite{GK-joints, KSS}.
Alex Vardy and Abdul Basit independently suggested to me that bounds on the joints problem
could potentially be improved using the method of multiplicities. The $m$-line decoding algorithm
for multiplicity codes can be used to give a multiplicity-enhanced proof of the~\cite{KSS}
bound on the joints problem; unfortunately this variant does not improve on the bounds.

A brief outline of the argument goes as follows. One first interpolates a low degree
polynomial vanishing with multiplicity
 at least $a$ at the joints of interest (for some large $a$). Then one argues that this polynomial vanishes at each line
of the collection with multiplicity at least some $c$. Then using Lemma~\ref{lem:joints2}, we deduce
that this polynomial actually vanishes at each of the joints with multiplicity at least $c' \gg a$.
This leads to a contradiction, unless the number of joints is large.


\item The Reed-Muller codes over small fields and in
many variables have been very influential.
The analogous multiplicity
code would be based on order $s$ evaluations of polynomials over
$\F_q$ of total degree at most $d$ and individual degree at most
$sq- 1$. It would
be very interesting to study properties of these codes, and to see
if they have any coding/combinatorial applications.

We note