Binary linear LTC 

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

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) 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) (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”, Property Testing 211 (2010) DOI
[8]
N. Alon et al., “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 et al., “Optimal Testing of Reed-Muller Codes”, (2010) arXiv:0910.0641
Page edit log

Your contribution is welcome!

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

edit on this site

Zoo Code ID: binary_ltc

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

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.