Abstract
Multiplicity codes are a generalization of RS and RM codes where for each evaluation point we output the evaluation of a lowdegree polynomial and all of its directional derivatives up to order s. Multivariate multiplicity codes are locally decodable with the natural local decoding algorithm that reads values on a random line and corrects to the closest univariate 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 probabilistic algorithm that queries few symbols of a word c, accepts every c in the code with probability 1, and rejects every c not in the code with nonzero probability.
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 < qs1 for prime q. In addition, we show the sdimensional test is a local tester for multiplicity codes, when s < q. Combining the two results, we show our main result that the plane test is a local tester for multiplicity codes of degree d < qs1, with constant rejection probability for constant q, s.
Our technique is new. We represent the given input as a possibly very highdegree polynomial, and we show that for some choice of plane, the restriction of the polynomial to the plane is a highdegree bivariate 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 nonstandard monomial order for the argument to work.
BibTeX  Entry
@InProceedings{karliner_et_al:LIPIcs.CCC.2022.14,
author = {Karliner, Dan and Salama, Roie and TaShma, Amnon},
title = {{The Plane Test Is a Local Tester for Multiplicity Codes}},
booktitle = {37th Computational Complexity Conference (CCC 2022)},
pages = {14:114:33},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772419},
ISSN = {18688969},
year = {2022},
volume = {234},
editor = {Lovett, Shachar},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16576},
URN = {urn:nbn:de:0030drops165761},
doi = {10.4230/LIPIcs.CCC.2022.14},
annote = {Keywords: local testing, multiplicity codes, Reed Muller codes}
}
Keywords: 

local testing, multiplicity codes, Reed Muller codes 
Collection: 

37th Computational Complexity Conference (CCC 2022) 
Issue Date: 

2022 
Date of publication: 

11.07.2022 