The Plane Test Is a Local Tester for Multiplicity Codes
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.
local testing
multiplicity codes
Reed Muller codes
Theory of computation~Error-correcting codes
14:1-14:33
Regular Paper
https://eccc.weizmann.ac.il/report/2022/028/
We would like to thank Tali Kaufman and Noga Ron-Zewi for a stimulating discussion on the paper. In particular, we thank them for suggesting to utilize the approach for giving a new analysis of the RM characterization. Additionally, we would like to thank the referees to the submission of this paper for their insightful remarks and corrections.
Dan
Karliner
Dan Karliner
Department of Computer Science, Tel Aviv University, Israel
The research leading to these results was supported by Len Blavatnik and the Blavatnik Family foundation and by the Israel Science Foundation grant number 952/18.
Roie
Salama
Roie Salama
Department of Computer Science, Tel Aviv University, Israel
The research leading to these results was supported by Len Blavatnik and the Blavatnik Family foundation and by the Israel Science Foundation grant number 952/18.
Amnon
Ta-Shma
Amnon Ta-Shma
Department of Computer Science, Tel Aviv University, Israel
The research leading to these results was supported by the Israel Science Foundation grant number 952/18.
10.4230/LIPIcs.CCC.2022.14
Noga Alon. Combinatorial nullstellensatz. Combinatorics, Probability and Computing, 8(1-2):7-29, 1999.
Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, and Dana Ron. Testing reed-muller codes. IEEE Transactions on Information Theory, 51(11):4032-4039, 2005.
Simeon Ball and Oriol Serra. Punctured combinatorial nullstellensätze. Combinatorica, 29(5):511-522, 2009.
Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, and David Zuckerman. Optimal testing of reed-muller codes. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pages 488-497. IEEE, 2010.
David Cox, John Little, and Donal OShea. Ideals, varieties, and algorithms: an introduction to computational algebraic geometry and commutative algebra. Springer Science & Business Media, 2013.
Zeev Dvir, Swastik Kopparty, Shubhangi Saraf, and Madhu Sudan. Extensions to the method of multiplicities, with applications to kakeya sets and mergers. SIAM Journal on Computing, 42(6):2305-2328, 2013.
Katalin Friedl and Madhu Sudan. Some improvements to total degree tests. In Proceedings Third Israel Symposium on the Theory of Computing and Systems, pages 190-198. IEEE, 1995.
Peter Gemmell, Richard J. Lipton, Ronitt Rubinfeld, Madhu Sudan, and Avi Wigderson. Self-testing/correcting for polynomials and for approximate functions. In Cris Koutsougeras and Jeffrey Scott Vitter, editors, Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, May 5-8, 1991, New Orleans, Louisiana, USA, pages 32-42. ACM, 1991. URL: https://doi.org/10.1145/103418.103429.
https://doi.org/10.1145/103418.103429
Venkatesan Guruswami and Carol Wang. Linear-algebraic list decoding for variants of reed-solomon codes. IEEE Transactions on Information Theory, 59(6):3257-3268, 2013.
Elad Haramaty, Amir Shpilka, and Madhu Sudan. Optimal testing of multivariate polynomials over small prime fields. SIAM Journal on Computing, 42(2):536-562, 2013.
Charanjit S Jutla, Anindya C Patthak, Atri Rudra, and David Zuckerman. Testing low-degree polynomials over prime fields. In 45th Annual IEEE Symposium on Foundations of Computer Science, pages 423-432. IEEE, 2004.
Tali Kaufman and Dana Ron. Testing polynomials over general fields. SIAM Journal on Computing, 36(3):779-802, 2006.
Swastik Kopparty. Some remarks on multiplicity codes. Discrete Geometry and Algebraic Combinatorics, 625:155-176, 2013.
Swastik Kopparty, Or Meir, Noga Ron-Zewi, and Shubhangi Saraf. High-rate locally correctable and locally testable codes with sub-polynomial query complexity. Journal of the ACM (JACM), 64(2):1-42, 2017.
Swastik Kopparty, Shubhangi Saraf, and Sergey Yekhanin. High-rate codes with sublinear-time decoding. Journal of the ACM (JACM), 61(5):1-20, 2014.
Rasmus Refslund Nielsen. List decoding of linear block codes. PhD thesis, DTU, 2001.
M Yu Rosenbloom and Michael Anatol'evich Tsfasman. Codes for the m-metric. Problemy Peredachi Informatsii, 33(1):55-63, 1997.
Ronitt Rubinfeld and Madhu Sudan. Self-testing polynomial functions efficiently and over rational domains. In Greg N. Frederickson, editor, Proceedings of the Third Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 27-29 January 1992, Orlando, Florida, USA, pages 23-32. ACM/SIAM, 1992. URL: http://dl.acm.org/citation.cfm?id=139404.139410.
http://dl.acm.org/citation.cfm?id=139404.139410
Ronitt Rubinfeld and Madhu Sudan. Robust characterizations of polynomials with applications to program testing. SIAM Journal on Computing, 25(2):252-271, 1996.
Madhu Sudan, Luca Trevisan, and Salil Vadhan. Pseudorandom generators without the xor lemma. Journal of Computer and System Sciences, 62(2):236-266, 2001.
Dan Karliner, Roie Salama, and Amnon Ta-Shma
Creative Commons Attribution 4.0 International license
https://creativecommons.org/licenses/by/4.0/legalcode