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].
Parents
- Linear \(q\)-ary code — 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)\) [3]. This was later improved to codes with distance \(\frac{1}{2}n-O(n^{1-\gamma})\) for any positive \(\gamma\) [4], provided that the number of codewords is polynomial in \(n\).
- Locally testable code (LTC)
Children
- Ben-Sasson-Sudan code
- Meir code — Meir codes stand out in that they are based on a combinatorial construction, while other LTCs often use algebraic tools.
Cousins
- 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].
- Classical Goppa code — Goppa codes are locally testable [3].
- 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)\) [9].
- Bose–Chaudhuri–Hocquenghem (BCH) code — Duals of BCH codes are locally testable [3].
- Cyclic linear \(q\)-ary code — Cyclic linear codes cannot be \(c^3\)-LTCs [10]. Codeword symmetries are in general an obstruction to achieving such LTCs [11].
- Expander LP code — Classical codes resulting from the expander lifted-product construction are one of the first two families of \(c^3\)-LTCs.
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]
- T. Kaufman and S. Litsyn, “Almost Orthogonal Linear Codes are Locally Testable”, 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS’05) DOI
- [4]
- 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) (2007) DOI
- [5]
- L. Babai et al., “Checking computations in polylogarithmic time”, Proceedings of the twenty-third annual ACM symposium on Theory of computing - STOC ’91 (1991) DOI
- [6]
- S. Arora et al., “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 (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 (1997) DOI
- [9]
- E. Ben-Sasson and M. Sudan, “Short PCPs with Polylog Query Complexity”, SIAM Journal on Computing 38, 551 (2008) DOI
- [10]
- L. Babai, A. Shpilka, and D. Stefankovic, “Locally Testable Cyclic Codes”, IEEE Transactions on Information Theory 51, 2849 (2005) DOI
- [11]
- M. Sudan, “Invariance in Property Testing”, Property Testing 211 (2010) 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