Description
A binary linear code \(C\) of length \(n\) that is a \((u,R)\)-LTC with query complexity \(u\) and soundness \(R>0\).
More technically, the code is a \((u,R)\)-LTC if the rows of its parity-check matrix \(H\in \mathbb{F}_2^{r\times n}\) have weight at most \(u\) and if \begin{align}
Cousins
- Cyclic linear binary code— Cyclic linear codes cannot be \(c^3\)-LTCs [2]. Codeword symmetries are in general an obstruction to achieving such LTCs [3].
- Reed-Muller (RM) code— RM codes can be LTCs in the low- [4,5] and high-error [6] regimes; see also [7].
Member of code lists
Primary Hierarchy
References
- [1]
A. Leverrier, V. Londe, and G. Zémor, “Towards local testability for quantum coding”, Quantum 6, 661 (2022) arXiv:1911.03069 DOI
- [2]
L. Babai, A. Shpilka, and D. Stefankovic, “Locally Testable Cyclic Codes”, IEEE Transactions on Information Theory 51, 2849 (2005) DOI
- [3]
M. Sudan, “Invariance in Property Testing”, Lecture Notes in Computer Science 211 (2010) DOI
- [4]
N. Alon, T. Kaufman, M. Krivelevich, S. Litsyn, and D. Ron, “Testing Reed–Muller Codes”, IEEE Transactions on Information Theory 51, 4032 (2005) DOI
- [5]
T. Kaufman and D. Ron, “Testing Polynomials over General Fields”, SIAM Journal on Computing 36, 779 (2006) DOI
- [6]
A. Samorodnitsky, “Low-degree tests at large distances”, (2006) arXiv:math/0604353
- [7]
A. Bhattacharyya, S. Kopparty, G. Schoenebeck, M. Sudan, and D. Zuckerman, “Optimal Testing of Reed-Muller Codes”, (2010) arXiv:0910.0641
- [8]
T. Kaufman and S. Litsyn, “Almost Orthogonal Linear Codes are Locally Testable”, 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS’05) 317 DOI
- [9]
T. Kaufman and M. Sudan, “Sparse Random Linear Codes are Locally Decodable and Testable”, 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07) 590 (2007) DOI
- [10]
M. Blum, M. Luby, and R. Rubinfeld, “Self-testing/correcting with applications to numerical problems”, Proceedings of the twenty-second annual ACM symposium on Theory of computing - STOC ’90 73 (1990) DOI
- [11]
M. Blum, M. Luby, and R. Rubinfeld, “Self-testing/correcting with applications to numerical problems”, Journal of Computer and System Sciences 47, 549 (1993) DOI
Page edit log
- Victor V. Albert (2026-06-08) — most recent
- Victor V. Albert (2022-09-30)
Cite as:
“Binary linear LTC”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2026. https://errorcorrectionzoo.org/c/binary_ltc, arXiv:2606.11484
Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/bits/ltc/binary_ltc.yml.