Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR22-028 | 23rd February 2022 14:58

The plane test is a local tester for Multiplicity Codes


Authors: Dan Karliner, Roie Salama, Amnon Ta-Shma
Publication: 23rd February 2022 17:19
Downloads: 641


Multiplicity codes are a generalization of RS and RM codes where for each evaluation point we output the evaluation of a low-degree polynomial and all of its directional derivatives up to order $s$. Multi-variate multiplicity codes are locally decodable with the natural local decoding algorithm that reads values on a random line and corrects to the closest uni-variate multiplicity code. However, it was not known whether multiplicity codes are locally testable, and this question has been posed since the introduction of these codes with no progress up to date. In fact, it has been also open whether multiplicity codes can be characterized by local constraints, i.e., if there exists a subset $B$ such that $c$ is in the code iff $c \cdot z=0$ for any $z\in B$, and,
every $z \in B$ has small Hamming weight, i.e., few non-zero symbols.

We begin by giving a simple example showing the line test does not give local characterization when $d>q$. Surprisingly,
we then show the plane test is a local characterization when $s<q$ and $d<qs-1$ for prime $q$.
In addition, we show the $k$-dimensional test is a local tester for multiplicity codes, when $s < q$ and $k$ is at least $\lceil \frac{d+1}{q-1} \rceil$.
Combining the two results, we show that the plane test is a local tester for multiplicity codes, with constant rejection probability for constant $s$.

Our technique is new. We represent the given input as a possibly very high-degree polynomial, and we show that for some choice of plane, the restriction of the polynomial to the plane is a high-degree bi-variate polynomial. The argument has to work modulo the appropriate kernels, and for that we use Grobner theory, the Combinatorial Nullstellensatz theorem and its generalization to multiplicities. Even given that, the argument is delicate and requires choosing a non-standard monomial order for the argument to work.

ISSN 1433-8092 | Imprint