Description
A generalization of an \(m\)-variate polynomial evaluation code based on evaluating polynomials and \(s\) of their derivatives at all points in \(GF(q)^m\). Originally proposed for coding using the Rosenbloom-Tsfasman metric [1]. Univariate (\(m=1\)) [1,2] and multivariante (\(m>1\)) [3] codes have been proposed.
Protection
The multiplicity Schwartz-Zippel Lemma provides a lower bound on code distance [4].
Decoding
Multivariate multiplicity codes can be decoded up to half of the minimum distance in polynomial time [5,6].Univariate [2] and multivariate [5] multiplicity codes can be list-decoded up to the Johnson bound. Certain univariate code families achieve the list-decoding capacity for sufficiently large field characteristic [5,7].
Notes
See Ref. [8] for a review of multiplicity codes.
Parent
- Group-algebra code — Multiplicity codes of order \(s\) are Abelian group-algebra codes whose corresponding polynomial that is modded out is \((x-\alpha_j)^s\) for each evaluation point \(\alpha_j\) [9].
Children
- Generalized RM (GRM) code — Multivariate multiplicity codes of degree \(s=1\) reduce to GRM codes.
- Reed-Solomon (RS) code — Univariate multiplicity codes of degree \(s=1\) reduce to RS codes.
Cousins
- \(q\)-ary linear LCC — There exist multiplicity codes with rate arbitrarily close to one that are locally decodable and locally correctable from a constant error fraction [3].
- Locally testable code (LTC) — Some multiplicity codes are locally testable by an appropriate test [10,11].
References
- [1]
- M. Yu. Rosenbloom, M. A. Tsfasman, “Codes for the m-Metric”, Probl. Peredachi Inf., 33:1 (1997), 55–63; Problems Inform. Transmission, 33:1 (1997), 45–52
- [2]
- Rasmus R. Nielsen. List decoding of linear block codes. PhD thesis, Technical University of Denmark, 2001
- [3]
- S. Kopparty, S. Saraf, and S. Yekhanin, “High-rate codes with sublinear-time decoding”, Journal of the ACM 61, 1 (2014) DOI
- [4]
- Z. Dvir et al., “Extensions to the Method of Multiplicities, with applications to Kakeya Sets and Mergers”, (2009) arXiv:0901.2529
- [5]
- S. Kopparty, Theory of Computing 11, 149 (2015) DOI
- [6]
- S. Bhandari et al., “Decoding multivariate multiplicity codes on product sets”, Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (2021) arXiv:2012.01530 DOI
- [7]
- V. Guruswami and C. Wang, “Optimal rate list decoding via derivative codes”, (2011) arXiv:1106.3951
- [8]
- S. Kopparty, “Some remarks on multiplicity codes”, (2015) arXiv:1505.07547
- [9]
- S. Bhandari et al., “Ideal-Theoretic Explanation of Capacity-Achieving Decoding”, (2021) arXiv:2103.07930 DOI
- [10]
- D. Karliner, R. Salama, and A. Ta-Shma, “The Plane Test Is a Local Tester for Multiplicity Codes”, (2022) DOI
- [11]
- D. Karliner and A. Ta-Shma, “Improved Local Testing for Multiplicity Codes”, (2022) DOI
Page edit log
- Victor V. Albert (2024-01-26) — most recent
Cite as:
“Multiplicity code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2024. https://errorcorrectionzoo.org/c/multiplicity