Improved Local Testing for Multiplicity Codes

Authors Dan Karliner, Amnon Ta-Shma



PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2022.11.pdf
  • Filesize: 0.75 MB
  • 19 pages

Document Identifiers

Author Details

Dan Karliner
  • Department of Computer Science, Tel Aviv University, Israel
Amnon Ta-Shma
  • Department of Computer Science, Tel Aviv University, Israel

Cite AsGet BibTex

Dan Karliner and Amnon Ta-Shma. Improved Local Testing for Multiplicity Codes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 11:1-11:19, Schloss Dagstuhl – Leibniz-Zentrum fΓΌr Informatik (2022)
https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2022.11

Abstract

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 𝔽_p^m. Similarly to Reed-Muller codes, multiplicity codes have a local nature that allows for local correction and local testing. Recently, [Karliner et al., 2022] 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 tight analysis. In particular, we show that multiplicity codes 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 [Karliner et al., 2022] in the case of planes. Our analysis relies on a generalization of the technique of canonincal monomials introduced in [Haramaty et al., 2013]. Generalizing canonical monomials to the multiplicity case requires substantially different proofs which exploit the algebraic structure of multiplicity codes.

Subject Classification

ACM Subject Classification
  • Theory of computation β†’ Error-correcting codes
Keywords
  • local testing
  • multiplicity codes
  • Reed Muller codes

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. 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. Google Scholar
  2. 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. Google Scholar
  3. 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. Google Scholar
  4. 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. Google Scholar
  5. 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. Google Scholar
  6. Dan Karliner, Roie Salama, and Amnon Ta-Shma. The plane test is a local tester for multiplicity codes. preprint, 2022. URL: https://eccc.weizmann.ac.il/report/2022/028/.
  7. Tali Kaufman and Dor Minzer. Improved optimal testing results from global hypercontractivity, 2022. URL: http://arxiv.org/abs/2202.08688.
  8. Tali Kaufman and Dana Ron. Testing polynomials over general fields. SIAM Journal on Computing, 36(3):779-802, 2006. Google Scholar
  9. Tali Kaufman and Madhu Sudan. Algebraic property testing: the role of invariance. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 403-412, 2008. Google Scholar
  10. Swastik Kopparty. Some remarks on multiplicity codes. Discrete Geometry and Algebraic Combinatorics, 625:155-176, 2013. Google Scholar
  11. Swastik Kopparty, Shubhangi Saraf, and Sergey Yekhanin. High-rate codes with sublinear-time decoding. Journal of the ACM (JACM), 61(5):1-20, 2014. Google Scholar
  12. Rasmus Refslund Nielsen. List decoding of linear block codes. PhD thesis, DTU, 2001. Google Scholar
  13. M Yu Rosenbloom and Michael Anatol'evich Tsfasman. Codes for the m-metric. Problemy Peredachi Informatsii, 33(1):55-63, 1997. Google Scholar
  14. Ronitt Rubinfeld and Madhu Sudan. Robust characterizations of polynomials with applications to program testing. SIAM Journal on Computing, 25(2):252-271, 1996. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail