Locally testable code: Difference between revisions

Revision as of 05:29, 13 February 2010

Revision as of 14:59, 13 October 2010

Line 2:

{{Unreferenced|date=March 2009}}

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|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 proof (complexity)|probabilistically checkable proofs]].

The related [[locally decodable code]]s 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==