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(δ) (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 - δ.