Revision as of 14:59, 13 October 2010 edit Ylloh (talk \| contribs) Extended confirmed users 913 edits added link to locally decodable codes ← Previous edit		Revision as of 09:18, 14 October 2010 edit undo Ylloh (talk \| contribs) Extended confirmed users 913 edits m corrected relation to locally decodable Next edit →
Line 6: Locally testable codes have applications in [[average-case complexity]] and the design of [[probabilistically checkable proof (complexity)\|probabilistically checkable proofs]]. ~~The related~~ [[~~locally~~Locally decodable code]]s are closely related to locally testable codes, ~~which~~ in ~~addition~~that they make ~~allow~~it possible to decode single bits of the ~~string encoded by the codeword~~message by only looking at few positions of ~~the~~a possibly corrupted codeword. ==Definition==

Locally testable code: Difference between revisions