Locally testable code: Difference between revisions

Revision as of 08:16, 10 December 2021

Latest revision as of 23:25, 9 January 2024

(5 intermediate revisions by 4 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 30 ⟶ 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>{{cite arxivarXiv|last1=Panteleev|first1=Pavel|last2=Kalachev|first2=Gleb|date=2021-11-05|title=Asymptotically Good Quantum and Locally Testable Classical LDPC Codes|class=cs.IT|eprint=2111.03654}}</ref><ref>{{cite arxivarXiv|last1=Dinur|first1=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|class=cs.IT|eprint=2111.04808}}</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 71 ⟶ 72:

== 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|url-status=live|access-date=|website=simons.berkeley.edu}}

[[Category:Error detection and correction]]