Description
A \(q\)-ary 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(q)^{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 \(q\)-ary string \(x\), where \(D(x,C)\) is the \(q\)-ary Hamming distance between \(x\) and the closest codeword to \(x\) [1; Def. 11]. A code satisfying the above constraint without the weight-\(u\) restriction is called an \(R\)-testable code [2].Notes
Testable binary codes admit weakly stable presentations of their correspoding groups; this property is relevant to the disproof of the Connes embedding conjecture [2].Cousins
- Reed-Solomon (RS) code— RS codes can be used to construct LTCs encoding \(k\) bits with length \(k \text{polylog}(k)\) and query complexity \(\text{polylog}(k)\) [3].
- Goppa code— Goppa codes are locally testable [4].
- Generalized RM (GRM) code— GRM codes for \(r<q\) can be LTCs in the low- [5,6] and high-error [7,8] regimes. They admit weakly stable presentations of their corresponding groups [2].
- Bose–Chaudhuri–Hocquenghem (BCH) code— Duals of BCH codes are locally testable [4].
- Cyclic linear \(q\)-ary code— Cyclic linear codes cannot be \(c^3\)-LTCs [9]. Codeword symmetries are in general an obstruction to achieving such LTCs [10].
- Galois-qudit expander code— Balanced products of expander codes with RS inner codes yield \([q^{\text{polylog}(q)},k\geq n^{1-\epsilon},n/\text{poly}(\log n)]_q\) LTCs exhibiting the multiplication property [11].
- Expander LP code— Classical codes resulting from the expander lifted-product construction are one of the first two families of \(c^3\)-LTCs [12].
Member of code lists
Primary Hierarchy
Parents
Linear \(q\)-ary 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\) [13], provided that the number of codewords is polynomial in \(n\).
\(q\)-ary linear LTC
Children
Meir codes stand out in that they are based on a combinatorial construction, while other LTCs often use algebraic tools.
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. Chapman, T. Vidick, and H. Yuen, “Efficiently stable presentations from error-correcting codes”, (2023) arXiv:2311.04681
- [3]
- E. Ben-Sasson and M. Sudan, “Short PCPs with Polylog Query Complexity”, SIAM Journal on Computing 38, 551 (2008) 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]
- L. Babai, L. Fortnow, L. A. Levin, and M. Szegedy, “Checking computations in polylogarithmic time”, Proceedings of the twenty-third annual ACM symposium on Theory of computing - STOC ’91 21 (1991) DOI
- [6]
- S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy, “Proof verification and the hardness of approximation problems”, Journal of the ACM 45, 501 (1998) DOI
- [7]
- R. Raz and S. Safra, “A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP”, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing - STOC ’97 475 (1997) DOI
- [8]
- S. Arora and M. Sudan, “Improved low-degree testing and its applications”, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing - STOC ’97 485 (1997) DOI
- [9]
- L. Babai, A. Shpilka, and D. Stefankovic, “Locally Testable Cyclic Codes”, IEEE Transactions on Information Theory 51, 2849 (2005) DOI
- [10]
- M. Sudan, “Invariance in Property Testing”, Lecture Notes in Computer Science 211 (2010) DOI
- [11]
- L. Golowich and T.-C. Lin, “Quantum LDPC Codes with Transversal Non-Clifford Gates via Products of Algebraic Codes”, (2024) arXiv:2410.14662
- [12]
- P. Panteleev and G. Kalachev, “Asymptotically Good Quantum and Locally Testable Classical LDPC Codes”, (2022) arXiv:2111.03654
- [13]
- 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
Page edit log
- Victor V. Albert (2022-09-30) — most recent
Cite as:
“\(q\)-ary linear LTC”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/q-ary_ltc