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.

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

Definition

A family of error-correcting codes C_n ⊆ {0, 1}ⁿ is locally testable with soundness s(n, δ), 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(1ⁿ)^y accepts with probability 1.
• Soundness: If the Hamming distance between y and C is δn, then T(1ⁿ)^y accepts with probability at most s(n, ε).

Examples

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