License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2022.14
URN: urn:nbn:de:0030-drops-165761
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16576/
Karliner, Dan ;
Salama, Roie ;
Ta-Shma, Amnon
The Plane Test Is a Local Tester for Multiplicity Codes
Abstract
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 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 < qs-1 for prime q. In addition, we show the s-dimensional 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 < qs-1, with constant rejection probability for constant q, 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.
BibTeX - Entry
@InProceedings{karliner_et_al:LIPIcs.CCC.2022.14,
author = {Karliner, Dan and Salama, Roie and Ta-Shma, Amnon},
title = {{The Plane Test Is a Local Tester for Multiplicity Codes}},
booktitle = {37th Computational Complexity Conference (CCC 2022)},
pages = {14:1--14:33},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-241-9},
ISSN = {1868-8969},
year = {2022},
volume = {234},
editor = {Lovett, Shachar},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16576},
URN = {urn:nbn:de:0030-drops-165761},
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 |
