Locally testable code: Difference between revisions

Revision as of 19:50, 11 December 2013

Revision as of 13:41, 14 January 2014

Line 3:

In contrast, [[locally decodable code]]s use a small number of bits of the codeword to [[Probabilistic Turing Machine|probabilistically]] recover the original information. The fraction of errors determines how likely it is that the decoder correctly recovers the original bit; however, not all locally decodable codes are locally testable.<ref name=decNotTest>{{cite web|url=http://eccc.hpi-web.de/report/2010/130/revision/1/download/|title=Locally Testable vs. Locally Decodable Codes|author=Tali Kaufman, Michael Viderman}}</ref>

Clearly, any valid codeword should be accepted as a codeword, but strings that are not codewords could be only one bit off, which would require many (certainly more than a constant number) of probes. To account for this, testing failure is only defined if the string is off by at least a set fraction of its bits. This implies words of the code must be longer than the input strings by adding some redundancy.

== Definition ==