ECCC-Report TR22-028https://eccc.weizmann.ac.il/report/2022/028Comments and Revisions published for TR22-028en-usWed, 23 Feb 2022 17:19:21 +0200
Paper TR22-028
| The plane test is a local tester for Multiplicity Codes |
Dan Karliner,
Amnon Ta-Shma,
Roie Salama
https://eccc.weizmann.ac.il/report/2022/028Multiplicity 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.Wed, 23 Feb 2022 17:19:21 +0200https://eccc.weizmann.ac.il/report/2022/028