Locally testable code (LTC)[14] 

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,711]; see Ref. [5] for a review.

Parent

Children

Cousins

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]
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]
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 (2010) DOI
[16]
T.-C. Lin and M.-H. Hsieh, “\(c^3\)-Locally Testable Codes from Lossless Expanders”, (2022) arXiv:2201.11369
Page edit log

Your contribution is welcome!

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

edit on this site

Zoo Code ID: ltc

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

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/edit/main/codes/classical/properties/ltc/ltc.yml.