Multiplicity code[13] 

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

Cousins

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
[12]
H. Asi and E. Yaakobi, “Nearly Optimal Constructions of PIR and Batch Codes”, (2017) arXiv:1701.07206
Page edit log

Your contribution is welcome!

on github.com (edit & pull request)— see instructions

edit on this site

Zoo Code ID: multiplicity

Cite as:
“Multiplicity code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2024. https://errorcorrectionzoo.org/c/multiplicity
BibTeX:
@incollection{eczoo_multiplicity, title={Multiplicity code}, booktitle={The Error Correction Zoo}, year={2024}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/multiplicity} }
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/multiplicity

Cite as:

“Multiplicity code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2024. https://errorcorrectionzoo.org/c/multiplicity

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/q-ary_digits/ag/multiplicity.yml.