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 GF(2)^{r\times n}\) have weight at most \(u\) and if \begin{align} \frac{1}{r}|H x| \geq \frac{R}{n} D(x,C) \tag*{(1)}\end{align} holds for any bitstring \(x\), where \(D(x,C)\) is the Hamming distance between \(x\) and the closest codeword to \(x\) [1; Def. 11].
Parents
Children
- Hadamard code — The Hadamard code is the first code to be identified as a (three-query) LTC [2,3].
- Ben-Sasson-Goldreich-Harsha-Sudan-Vadhan (BGHSV) code
- Ben-Sasson-Sudan-Vadhan-Wigderson (BSVW) code
- Dinur code
- Goldreich-Sudan code — Goldreich-Sudan codes resulted from what is often referred to as the first systematic study of LTCs.
- Kopparty-Meir-Ron-Zewi-Saraf (KMRS) code
- Long code
- Left-right Cayley complex code — Left-right Cayley complex codes yield one of the first two families of \(c^3\)-LTCs.
Cousins
- Linear binary code — Linear binary codes with distances \(\frac{1}{2}n-\sqrt{t n}\) for some \(t\) are called almost-orthogonal and are locally testable with query complexity of order \(O(t)\) [4]. This was later improved to codes with distance \(\frac{1}{2}n-O(n^{1-\gamma})\) for any positive \(\gamma\) [5], provided that the number of codewords is polynomial in \(n\).
- Cyclic linear binary code — Cyclic linear codes cannot be \(c^3\)-LTCs [6]. Codeword symmetries are in general an obstruction to achieving such LTCs [7].
- Reed-Muller (RM) code — RM codes can be LTCs in the low- [8,9] and high-error [10] regimes; see also [11].
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]
- 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 (1990) DOI
- [3]
- 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
- [4]
- 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
- [5]
- 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
- [6]
- L. Babai, A. Shpilka, and D. Stefankovic, “Locally Testable Cyclic Codes”, IEEE Transactions on Information Theory 51, 2849 (2005) DOI
- [7]
- M. Sudan, “Invariance in Property Testing”, Lecture Notes in Computer Science 211 (2010) DOI
- [8]
- N. Alon, T. Kaufman, M. Krivelevich, S. Litsyn, and D. Ron, “Testing Reed–Muller Codes”, IEEE Transactions on Information Theory 51, 4032 (2005) DOI
- [9]
- T. Kaufman and D. Ron, “Testing Polynomials over General Fields”, SIAM Journal on Computing 36, 779 (2006) DOI
- [10]
- A. Samorodnitsky, “Low-degree tests at large distances”, (2006) arXiv:math/0604353
- [11]
- A. Bhattacharyya, S. Kopparty, G. Schoenebeck, M. Sudan, and D. Zuckerman, “Optimal Testing of Reed-Muller Codes”, (2010) arXiv:0910.0641
Page edit log
- Victor V. Albert (2022-09-30) — most recent
Cite as:
“Binary linear LTC”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/binary_ltc
Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/bits/ltc/binary_ltc.yml.