Wikipedia / Locally testable code
Wikipedia / Locally testable code
A locally testable code is a type of error-correcting code for which it can be determined if a string is a 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 codes use a small number of bits of the codeword to 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.
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.
Definition
To measure the distance between two strings, the Hamming distance is used
is computed by
Relative distances are computed as a fraction of the number of bits
-testable if there exists a Turing machine M given random access and satisfies the following:
. In other words, M accepts given access to any codeword of C.
-far from C at least half the time.
Also the rate of a code is the ratio between its message length and codeword length
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":
.
is a function tending toward 0. This makes n closer to linear as k increases. For example:
These have both been achieved, even with constant query complexity and a binary alphabet. The next nearly linear goal is linear up to a polylogarithmic. Nobody has yet to come up with a linearly testable code that satisfies this constraint.
In November 2021 two preprints have reported.
Connection with probabilistically checkable proofs
Locally testable codes have a lot in common with probabilistically checkable proofs if it is part of the code. Many things can go wrong in assuming a PCP proof encodes a locally testable code. For example, the PCP definition says nothing about invalid proofs, only invalid inputs.
Despite this difference, locally testable codes and PCPs are similar enough that frequently to construct one, a prover will construct the other along the way.
Examples
Hadamard code
One of the most famous error-correcting codes, the Hadamard code for x and y uniformly random denotes bitwise XOR).
being incorrect. Let E be the event of exactly one of these occurring. This comes out to
. With additional work, it can be shown that the error is bounded by
, this only has a constant chance of false positives, so we can simply check a constant number of times to get the probability below 1/2.
Long code
The Long code. This violates the requirement that codewords are always accepted, but may be good enough for some needs.
Other locally testable codes include Reed-Muller codes (see locally decodable codes for a decoding algorithm), Reed-Solomon codes, and the short code.