\(q\)-ary linear LTC 

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

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- [3,4] and high-error [5,6] regimes. They admit weakly stable presentations of their correspoding groups [2].
  • Classical Goppa code — Goppa codes are locally testable [7].
  • 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)\) [8].
  • Bose–Chaudhuri–Hocquenghem (BCH) code — Duals of BCH codes are locally testable [7].
  • 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].
  • 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)\) [7]. This was later improved to codes with distance \(\frac{1}{2}n-O(n^{1-\gamma})\) for any positive \(\gamma\) [11], provided that the number of codewords is polynomial in \(n\).
  • 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]
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
[4]
S. Arora et al., “Proof verification and the hardness of approximation problems”, Journal of the ACM 45, 501 (1998) DOI
[5]
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
[6]
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
[7]
T. Kaufman and S. Litsyn, “Almost Orthogonal Linear Codes are Locally Testable”, 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS’05) DOI
[8]
E. Ben-Sasson and M. Sudan, “Short PCPs with Polylog Query Complexity”, SIAM Journal on Computing 38, 551 (2008) 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”, Property Testing 211 (2010) DOI
[11]
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
Page edit log

Your contribution is welcome!

on github.com (edit & pull request)— see instructions

edit on this site

Zoo Code ID: q-ary_ltc

Cite as:
\(q\)-ary linear LTC”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/q-ary_ltc
BibTeX:
@incollection{eczoo_q-ary_ltc, title={\(q\)-ary linear LTC}, booktitle={The Error Correction Zoo}, year={2022}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/q-ary_ltc} }
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/q-ary_ltc

Cite as:

\(q\)-ary linear LTC”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/q-ary_ltc

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/q-ary_digits/distributed_storage/ltc/q-ary_ltc.yml.