Locally testable code: Difference between revisions

Revision as of 14:41, 27 November 2021

Latest revision as of 23:25, 9 January 2024

(9 intermediate revisions by 6 users not shown)

Line 1:

{{Short description|Type of error-correcting code}}

A '''locally testable code''' is a type of [[error-correcting code]] for which it can be determined if a [[String (computer science)|string]] is a [[Code word (communication)|word]] in that code by looking at a small (frequently constant) number of bits of the string. In some situations, it is useful to know if the data is corrupted without decoding all of it so that appropriate action can be taken in response. For example, in communication, if the receiver encounters a corrupted code, it can request the data be re-sent, which could increase the accuracy of said data. Similarly, in data storage, these codes can allow for damaged data to be recovered and rewritten properly.

In contrast, [[locally decodable code]]s use a small number of bits of the codeword to [[Probabilistic Turing Machine|probabilistically]] recover the original information. The fraction of errors determines how likely it is that the decoder correctly recovers the original bit; however, not all locally decodable codes are locally testable.<ref name=decNotTest>{{cite web|url=http://eccc.hpi-web.de/report/2010/130/revision/1/download/|title=Locally Testable vs. Locally Decodable Codes|first1=Tali|last1=Kaufman|author1-link=Tali Kaufman|first2=Michael|last2=Viderman}}</ref>

Clearly, any valid codeword should be accepted as a codeword, but strings that are not codewords could be only one bit off, which would require many (certainly more than a constant number) probes. To account for this, testing failure is only defined if the string is off by at least a set fraction of its bits. This implies words of the code must be longer than the input strings by adding some redundancy.

Line 12 ⟶ 13:

Relative distances are computed as a fraction of the number of bits

:<math>\delta(x,y)=\Delta(x,y)/n \text{ and } \delta(w,C)=\Delta(w,C)/n</math>

A code <math>C:\{0,1\}^k\to\{0,1\}^n</math> is called <math>q</math>-local <math>\delta</math>-testable if there exists a Turing machine M given [[random access]] to an input <math>w</math> that makes at most <math>q</math> non-adaptive queries of <math>w</math> and satisfies the following:<ref name=robustLTC>{{cite web|url=http://people.csail.mit.edu/madhu/papers/2004/rltc-conf.pdf|title=Robust Locally Testable Codes and Products of Codes|first1=Eli|last1=Ben-Sasson|first2=Madhu|last2=Sudan}}</ref>

:* For any <math>x\in\{0,1\}^k</math> and <math>w=C(x)</math>, <math>Pr[M^w(1^k)=1]=1</math>. In other words, M accepts given access to any codeword of C.

:* For <math>w\in\{0,1\}^n</math> such that <math>\delta(w,C)>\delta</math>, <math>Pr[M^w(1^k)=1]\leq1/2</math>. M must reject strings <math>\delta</math>-far from C at least half the time.

Also the rate of a code is the ratio between its message length and codeword length

:<math>r=\frac{|x|}{|C(x)|}</math>

== Limits ==

It remains an open question whether there are any locally testable codes of linear size, but there are several constructions that are considered "nearly linear":<ref name=shortLTC>{{cite web|url=http://eccc.hpi-web.de/eccc-reports/2005/TR05-014/index.html|title=Short Locally Testable Codes and Proofs (Survey)|first=Oded|last=Goldreich|year=2005|citeseerx = 10.1.1.110.2530}}</ref>

# Polynomial arbitrarily close to linear; for any <math>\epsilon>0</math>, <math>n=k^{1+\epsilon}</math>.

Line 29 ⟶ 31:

The next nearly linear goal is linear up to a [[polylogarithmic]] factor; <math>n=\text{poly}(\log k)*k</math>. Nobody has yet to come up with a linearly testable code that satisfies this constraint.<ref name=shortLTC/>

In November 2021 two preprints have reported<ref>{{Citecite journalarXiv|lastlast1=Panteleev|firstfirst1=Pavel|last2=Kalachev|first2=Gleb|date=2021-11-05|title=Asymptotically Good Quantum and Locally Testable Classical LDPC Codes|urlclass=http://arxivcs.org/abs/2111.03654IT|journaleprint=arXiv:2111.03654 [quant-ph]}}</ref><ref>{{Citecite journalarXiv|lastlast1=Dinur|firstfirst1=Irit|author-link=Irit Dinur|last2=Evra|first2=Shai|author-link2=Shai Evra|last3=Livne|first3=Ron|last4=Lubotzky|first4=Alexander|author-link4=Alexander Lubotzky|last5=Mozes|first5=Shahar|author-link5=Shahar Mozes|date=2021-11-08|title=Locally Testable Codes with constant rate, distance, and locality|urlclass=http://arxivcs.org/abs/2111.04808IT|journaleprint=arXiv:2111.04808 [cs, math]}}</ref><ref>{{Cite web|last=Rorvig|first=Mordechai|date=2021-11-24|title=Researchers Defeat Randomness to Create Ideal Code|url=https://www.quantamagazine.org/researchers-defeat-randomness-to-create-ideal-code-20211124/|url-status=live|access-date=2021-11-24|website=[[Quanta Magazine]]|language=en}}</ref><ref>{{Cite web|last=Rorvig|first=Mordechai|date=2022-01-06|title=Qubits Can Be as Safe as Bits, Researchers Show|url=https://www.quantamagazine.org/qubits-can-be-as-safe-as-bits-researchers-show-20220106/|access-date=2022-02-02|website=Quanta Magazine|language=en}}</ref> the first polynomial-time construction of "<math>c^3</math>-LTCs" namely locally testable codes with constant rate <math>r</math>, constant distance <math>\delta</math> and constant locality <math>q</math>.

== Connection with probabilistically checkable proofs ==

Line 68 ⟶ 69:

== References ==

{{reflist}}

== External links ==

*{{Cite web|date=6 October 2021|title=Breakthroughs — Locally Testable Codes with Constant Rate, Distance, and Locality {{!}} Simons Institute for the Theory of Computing|url=https://simons.berkeley.edu/events/breakthroughs-locally-testable-codes-constant-rate-distance-and-locality|access-date=|website=simons.berkeley.edu}}

[[Category:Error detection and correction]]