Multiplicity code[13] 


A generalization of an \(m\)-variant 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.


The multiplicity Schwartz-Zippel Lemma provides a lower bound on code distance [4].


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].


See Ref. [8] for a review of multiplicity codes.


  • Linear \(q\)-ary code
  • 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].



  • \(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].


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
Rasmus R. Nielsen. List decoding of linear block codes. PhD thesis, Technical University of Denmark, 2001
S. Kopparty, S. Saraf, and S. Yekhanin, “High-rate codes with sublinear-time decoding”, Journal of the ACM 61, 1 (2014) DOI
Z. Dvir et al., “Extensions to the Method of Multiplicities, with applications to Kakeya Sets and Mergers”, (2009) arXiv:0901.2529
S. Kopparty, Theory of Computing 11, 149 (2015) DOI
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
V. Guruswami and C. Wang, “Optimal rate list decoding via derivative codes”, (2011) arXiv:1106.3951
S. Kopparty, “Some remarks on multiplicity codes”, (2015) arXiv:1505.07547
S. Bhandari et al., “Ideal-Theoretic Explanation of Capacity-Achieving Decoding”, (2021) arXiv:2103.07930 DOI
D. Karliner, R. Salama, and A. Ta-Shma, “The Plane Test Is a Local Tester for Multiplicity Codes”, (2022) DOI
D. Karliner and A. Ta-Shma, “Improved Local Testing for Multiplicity Codes”, (2022) DOI
Page edit log

Your contribution is welcome!

on (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.
@incollection{eczoo_multiplicity, title={Multiplicity code}, booktitle={The Error Correction Zoo}, year={2024}, editor={Albert, Victor V. and Faist, Philippe}, url={} }
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:

Cite as:

“Multiplicity code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2024.