[Jump to code hierarchy]

Kopparty-Meir-Ron-Zewi-Saraf (KMRS) code[1,2]

Description

Member of a family of locally testable binary linear codes with constant rate, constant relative distance, and subpolynomial query complexity \(u = (\log n)^{O(\log \log n)}\). Later work by Gopi, Kopparty, Oliveira, Ron-Zewi, and Saraf [2] showed that related concatenated codes achieve the GV bound.

Member of code lists

Primary Hierarchy

Classical Domain
Binary Kingdom
Binary codeECC
Binary group-orbit codeECC
Linear binary codeLinear \(q\)-ary Linear code over \(\mathbb{Z}_q\) ECC
Binary linear LTCLinear \(q\)-ary LTC ECC
Parents
Binary linear LTC
Kopparty-Meir-Ron-Zewi-Saraf (KMRS) code

References

[1]
S. Kopparty, O. Meir, N. Ron-Zewi, and S. Saraf, “High-Rate Locally Correctable and Locally Testable Codes with Sub-Polynomial Query Complexity”, Journal of the ACM 64, 1 (2017) DOI
[2]
S. Gopi, S. Kopparty, R. Oliveira, N. Ron-Zewi, and S. Saraf, “Locally Testable and Locally Correctable Codes approaching the Gilbert-Varshamov Bound”, IEEE Transactions on Information Theory 64, 5813 (2018) DOI
Page edit log

Your contribution is welcome!

on github.com (edit & pull request)

— see instructions

Zoo Code ID: kmrs-ltc

Cite as:
“Kopparty-Meir-Ron-Zewi-Saraf (KMRS) code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2026. https://errorcorrectionzoo.org/c/kmrs-ltc, arXiv:2606.11484
BibTeX:
@incollection{eczoo_kmrs-ltc,
title={Kopparty-Meir-Ron-Zewi-Saraf (KMRS) code},
booktitle={The Error Correction Zoo},
year={2026},
editor={Albert, Victor V. and Faist, Philippe},
eprint={2606.11484},
doi={10.48550/arXiv.2606.11484},
url={https://errorcorrectionzoo.org/c/kmrs-ltc}
}
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/kmrs-ltc

Cite as:

“Kopparty-Meir-Ron-Zewi-Saraf (KMRS) code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2026. https://errorcorrectionzoo.org/c/kmrs-ltc, arXiv:2606.11484

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/bits/ltc/kmrs-ltc.yml.