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 an 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
LTCs first appeared implicitly in works on probabilistically checkable proofs (PCPs) [1,7–11]; see Ref. [5] for a review.Cousins
- Quantum locally testable code (QLTC)
- Locally decodable code (LDC)— There are relations between LDCs and LTCs [12].
- Locally correctable code (LCC)— There are relations between LDCs and LTCs [12].
- Multiplicity code— Some multiplicity codes are locally testable by an appropriate test [13,14].
- Tanner code— Tanner codes can be generalized to sheaf codes, whose local codes satisfy a certain hierarchy. This allows for a way to formulate and understand many generalized homological-product CSS codes [15] and LTCs [16].
- Balanced code— Random low-rate unbiased linear codes are LTCs [17].
- Hypergraph product (HGP) code— Applying the hypergraph product to an LTC yields a code which provides an explicit example of No Low-Error Trivial States (NLETS) [18].
- 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 [19].
Primary Hierarchy
References
- [1]
- 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
- [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”, Lecture Notes in Computer Science 65 (2010) DOI
- [6]
- I. Dinur, S. Evra, R. Livne, A. Lubotzky, and S. Mozes, “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, L. Fortnow, H. Karloff, and N. Nisan, “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, 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
- [12]
- T. Kaufman and M. Viderman, “Locally Testable vs. Locally Decodable Codes”, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques 670 (2010) DOI
- [13]
- D. Karliner, R. Salama, and A. Ta-Shma, “The Plane Test Is a Local Tester for Multiplicity Codes”, (2022) DOI
- [14]
- D. Karliner and A. Ta-Shma, “Improved Local Testing for Multiplicity Codes”, (2022) DOI
- [15]
- P. Panteleev and G. Kalachev, “Maximally Extendable Sheaf Codes”, (2024) arXiv:2403.03651
- [16]
- U. A. First and T. Kaufman, “Cosystolic Expansion of Sheaves on Posets with Applications to Good 2-Query Locally Testable Codes and Lifted Codes”, (2024) arXiv:2403.19388
- [17]
- S. Kopparty and S. Saraf, “Local list-decoding and testing of random linear codes from high error”, Proceedings of the forty-second ACM symposium on Theory of computing 417 (2010) DOI
- [18]
- L. Eldar and A. W. Harrow, “Local Hamiltonians Whose Ground States Are Hard to Approximate”, 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) 427 (2017) arXiv:1510.02082 DOI
- [19]
- 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