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.
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.
-testable if there exists a Turing machine M given random access to an input
and satisfies the following:[2] Also the rate of a code is the ratio between its message length and codeword length 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":[3] These have both been achieved, even with constant query complexity and a binary alphabet, such as with
Nobody has yet to come up with a linearly testable code that satisfies this constraint.
[3] In November 2021 two preprints have reported[4][5][6][7] the first polynomial-time construction of "
-LTCs" namely locally testable codes with constant rate
Locally testable codes have a lot in common with probabilistically checkable proofs (PCPs).
random nonadaptive queries into a large string and if we want to accept, we must with probability 1, and if not, we must accept no more than half the time.
The major difference is that PCPs are interested in accepting
Locally testable codes, on the other hand, accept
Many things can go wrong in assuming a PCP proof encodes a locally testable code.
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.
A codeword x is encoded in the Hadamard code to be the linear function
To test if a string w is a codeword of the Hadamard code, all we have to do is test if the function it encodes is linear.
, this equation is true, as that is the definition of a linear function.
-far from C will have an upper bound on its error in terms of
One bound is found by the direct approach of approximating the chances of exactly one of the three probes yielding an incorrect result.
With additional work, it can be shown that the error is bounded by For any given
, 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.
bits to represent), the function that returns the
The way to locally test this with some errors is to pick a uniformly random input
, but with a small chance of flipping each bit,
This violates the requirement that codewords are always accepted, but may be good enough for some needs.