Locally testable code

In theoretical computer science, a locally testable code is an error correcting code for which membership can be tested by a non-adaptive property testing algorithm. That is, locally testable codes have an efficient probabilistic algorithm that, based on its random bits, non-adaptively looks at few (e.g. a constant number of) positions of the message and can then determine with high probability whether the message is close to a codeword.

Locally testable codes have applications in average-case complexity and the design of probabilistically checkable proofs.

The related locally decodable codes are locally testable codes, which in addition allow to decode single bits of the string encoded by the codeword by only looking at few positions of the codeword.

Definition

A family of error-correcting codes C_n ⊆ {0, 1}ⁿ is locally testable with soundness s(δ) (where s(δ) < 1 for every δ > 0), and query complexity q(n) if there exists a non-adaptive oracle algorithm T (the tester) that on input 1ⁿ and given oracle access to a string y ∈ {0, 1}n satisfies the following:

• Completeness: If y ∈ C, then T^y(1ⁿ) accepts with probability 1.
• Soundness: If the Hamming distance between y and C is δn, then T^y(1ⁿ) accepts with probability at most s(δ).

In theoretical computer science, one is typically interested in locally testable codes whose query complexity is constant or at most logarithmic.

Examples

An example of a locally testable code is the Hadamard code. The Hadamard code is testable with 3 queries and soundness 1 - δ.