Description
Code for which one can efficiently check whether a given string is a codeword or is far from a codeword. Efficiency of the verification is quantified by the code's query complexity \(u\), while effectiveness is quantified by the code's soundness \(R\).
Typically, one looks at how \(R\) scales with increasing code size for infinite families of codes, defining LTC families as those for which the soundness is asymptotically constant. Such LTC families with asymptotically constant distance, rate, and query complexity are called \(c^3\)-LTCs. The first two such families are classical codes arising from the expander lifted-product quantum code construction and left-right Cayley complex codes.
A technical definition for codes over binary alphabets is provided as follows; for general alphabets, see Ref. [5]. The idea behind LTCs is to be able to reliably test whether a given bit-string \(x\) is in the code by only sampling subsets of \(u\) bits. To have something to check against, we first have to define a collection of length-\(u\) subsets \(S\) of bit locations that are called allowed local views. A code is LTC if the following two conditions are satisfied [6; Thm. 1.1].
First, if \(x\) is a codeword, then all of its restrictions \(x|_S\) to the subsets \(S\) are allowed local views, \begin{align} x\in C \Rightarrow x|_S \in \{\text{allowed local views}\}~. \tag*{(1)}\end{align} This guarantees that codewords can indeed be determined from this limited sampling procedure.
Second, the probability that a given restriction is not an allowed local view is lower-bounded by the relative distance to the code, \begin{align} \text{Pr}_S (x|_S\text{ not allowed local view}) \geq \frac{R}{n} D(x,C)~, \tag*{(2)}\end{align} where \(D(x,C)\) is the Hamming distance between \(x\) and the closest codeword to \(x\). This condition ensures that strings \(x\) can be deemed to be not in the codespace with high probability, i.e., with probability increasing as \(x\) gets farther from the code.
Notes
Parent
Children
Cousins
- Quantum locally testable code (QLTC)
- Locally decodable code (LDC) — There are relations between LDCs and LTCs [12].
- Balanced code — Random low-rate unbiased linear codes are LTCs [13].
- Lossless expander balanced-product code — Using one part of a quantum-code chain complex constructed with one-sided loss expanders yields a \(c^3\)-LTC [14].
References
- [1]
- 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
- [2]
- Sanjeev Arora. Probabilistic checking of proofs and hardness of approximation problems. UC Berkeley, 1994.
- [3]
- R. Rubinfeld and M. Sudan, “Robust Characterizations of Polynomials with Applications to Program Testing”, SIAM Journal on Computing 25, 252 (1996) DOI
- [4]
- K. Friedl and M. Sudan, “Some Improvements to Total Degree Tests”, (2013) arXiv:1307.3975
- [5]
- O. Goldreich, “Short Locally Testable Codes and Proofs: A Survey in Two Parts”, Property Testing 65 (2010) DOI
- [6]
- I. Dinur et al., “Locally Testable Codes with constant rate, distance, and locality”, (2021) arXiv:2111.04808
- [7]
- 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
- [8]
- L. Babai, L. Fortnow, and C. Lund, “Non-deterministic exponential time has two-prover interactive protocols”, Computational Complexity 1, 3 (1991) DOI
- [9]
- C. Lund et al., “Algebraic methods for interactive proof systems”, Journal of the ACM 39, 859 (1992) DOI
- [10]
- S. Arora and S. Safra, “Probabilistic checking of proofs”, Journal of the ACM 45, 70 (1998) DOI
- [11]
- S. Arora et al., “Proof verification and the hardness of approximation problems”, Journal of the ACM 45, 501 (1998) DOI
- [12]
- T. Kaufman and M. Viderman, “Locally Testable vs. Locally Decodable Codes”, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques 670 (2010) DOI
- [13]
- S. Kopparty and S. Saraf, “Local list-decoding and testing of random linear codes from high error”, Proceedings of the 42nd ACM symposium on Theory of computing - STOC ’10 (2010) DOI
- [14]
- T.-C. Lin and M.-H. Hsieh, “\(c^3\)-Locally Testable Codes from Lossless Expanders”, (2022) arXiv:2201.11369
Page edit log
- Victor V. Albert (2022-09-27) — most recent
Cite as:
“Locally testable code (LTC)”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/ltc
Github: https://github.com/errorcorrectionzoo/eczoo_data/tree/main/codes/classical/properties/ltc/ltc.yml.