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 The distance of a string formula_2 from a code formula_3 is computed by Relative distances are computed as a fraction of the number of bits A code formula_3 is called formula_7-local formula_8-testable if there exists a Turing machine M given random access to an input formula_2 that makes at most formula_7 non-adaptive  queries of formula_2 and satisfies the following: 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": These have both been achieved, even with constant query complexity and a binary alphabet, such as with formula_29 for any formula_26. The next nearly linear goal is linear up to a polylogarithmic factor; formula_31. Nobody has yet to come up with a linearly testable code that satisfies this constraint. In November  2021 two preprints have reported the first polynomial-time construction of "formula_32-LTCs" namely locally testable codes with constant rate formula_33, constant distance formula_8 and constant locality formula_7. Connection with probabilistically checkable proofs. Locally testable codes have a lot in common with probabilistically checkable proofs (PCPs). This should be apparent from the similarities of their construction. In both, we are given formula_7 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 formula_37 if there exists a formula_2 so that formula_39. Locally testable codes, on the other hand, accept formula_2 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, is a locally testable code. A  codeword x is encoded in the Hadamard code to be the linear function formula_41 (mod 2). This requires listing out the result of this function for every possible y, which requires exponentially more bits than its input. 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 means simply checking if formula_42 for x and y uniformly random vectors (where formula_43 denotes bitwise XOR). It is easy to see that for any valid encoding formula_2, this equation is true, as that is  the definition of a linear function. Somewhat harder, however, is showing that a string that is formula_8-far from C will have an upper bound on its error in terms of formula_8. One bound is found by the direct approach of approximating the chances of exactly one of the three probes yielding an incorrect result. Let A, B, and C be the events of formula_47, formula_48, and formula_49 being incorrect. Let E be the event of exactly one of these occurring. This comes out to This works for formula_51, but shortly after, formula_52. With additional work, it can be shown  that the error is bounded by For any given formula_8, 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 is another code with very large blowup which is close to locally testable. Given an input formula_55 (note, this takes formula_56 bits to represent), the function that returns the formula_57 bit of the input, formula_58, is evaluated on all possible formula_59-bit inputs formula_60, and the codeword is the concatenation of these (of length formula_61). The way to locally test  this with some errors is to pick a uniformly random input formula_37 and set formula_63, but with a small chance of flipping each bit, formula_64. Accept a function formula_65 as a codeword if formula_66. If formula_65 is a codeword, this will accept formula_65 as long as formula_69 was unchanged, which happens with probability formula_70. 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.