Locally testable code: Difference between revisions

Revision as of 05:17, 11 December 2013

Revision as of 05:41, 11 December 2013

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 at least 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 ==

Line 54:

=== Long code ===

The [[Long code]] is another code with very large blowup which is close to locally testable. Given an input <math>0\leq i\leq2^k</math> (note, this takes <math>k</math> bits to represent), the function that returns the <math>i^{th}</math> bit of the input, <math>f_i(x)=x_i</math>, is evaluated on all possible <math>2^k</math>-bit inputs <math>0\leq x\leq2^{2^k}</math>, and the codeword is the concatenation of these (of length <math>n=2^{2^k}</math>). The way to locally test this with some errors is to pick a uniformly random input <math>x</math> and set <math>y=x</math>, but with a small chance of flipping each bit, <math>\mu>0</math>. Accept a function <math>f</math> as a codeword if <math>f(x)=f(y)</math>. If <math>f</math> is a codeword, this will accept <math>f</math> as long as <math>x_i</math> was unchanged, which happens with probability <math>1-\mu</math>. This violates the requirement that codewords are always accepted, but may be good enough for some needs.<ref name=LongCode>{{cite web|url=http://www.wisdom.weizmann.ac.il/~ranraz/publications/Punique_codes.pdf|title=Bounds on Locally Testable Codes with Unique Tests|author=Gillat Kol, Ran Raz}}</ref>

Other locally testable codes include [[Reed-Muller codes]] (see [[locally decodable code]]s for a decoding algorithm), [[Reed-Solomon code]]s, and the short code.