Locally testable code: Difference between revisions

Revision as of 09:18, 14 October 2010

Revision as of 05:52, 26 November 2010

Line 1:

{{orphan|date=February 2010}}

{{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.