Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR22-078 | 8th May 2022 18:29

Improved local testing for multiplicity codes


Authors: Dan Karliner, Amnon Ta-Shma
Publication: 25th May 2022 06:48
Downloads: 448


Multiplicity codes are a generalization of Reed-Muller codes which include derivatives as well as the values of low degree polynomials, evaluated in every point in $\mathbb{F}_p^m$.
Similarly to Reed-Muller codes, multiplicity codes have a local nature that allows for local correction and local testing.
Recently, the authors and Salama showed that the plane test, which tests the degree of the codeword on a random plane, is a good local tester for small enough degrees.
In this work we simplify and extend the analysis of local testing for multiplicity codes, giving a more general and tighter analysis. In particular, we show that multiplicity codes $\mathrm{MRM}_{p}(m, d, s)$ over prime fields with arbitrary $d$ are locally testable by an appropriate $k$-flat test, which tests the degree of the codeword on a random $k$-dimensional affine subspace. The relationship between the degree parameter $d$ and the required dimension $k$ is shown to be nearly optimal, and improves on the degree previously known in the case of planes.

Our analysis relies on a generalization of the technique of canonincal monomials introduced by Haramaty, Shpilka and Sudan (FOCS 2011). Generalizing canonical monomials to the multiplicity case requires substantially different proofs which exploit the algebraic structure of multiplicity codes.

ISSN 1433-8092 | Imprint