Locally testable code: Difference between revisions

Revision as of 05:41, 11 December 2013

Revision as of 19:50, 11 December 2013

Line 1:

A '''Locallylocally testable code''' is a type of [[error-correcting code]] for which it can be determined if a [[String (computer science)|string]] is a [[Code word|word]] in that code by looking at a small (frequently constant) number of bits of the string. In some situations, it is useful to know if the data is corrupted without decoding all of it so that appropriate action can be taken in response. For example, in communication, if the receiver encounters a corrupted code, it can request the data be re-sent, which could increase the accuracy of said data. Similarly, in data storage, these codes can allow for damaged data to be recovered and rewritten properly.

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>

Line 18:

== Limits ==

It remains an open question whether there are any locally testable codes of linear size, but there are several constructions that come close. There are 3 different goals forconsidered "nearly linear":<ref name=shortLTC>{{cite web|url=http://eccc.hpi-web.de/eccc-reports/2005/TR05-014/index.html|title=Short Locally Testable Codes and Proofs (Survey)|author=Oded Goldreich}}</ref>

# Polynomial arbitrarily close to linear; for any <math>\epsilon>0</math>, <math>n=k^{1+\epsilon}</math>.

# Functions of the form <math>n=k^{1+\epsilon(k)}</math>, forwhere <math>\epsilon(k)\in o(1)</math>, meaningis a given function getstending toward 0. This makes n closer to linear as k increases. For example:

#* <math>1/\log \log k</math>

#* <math>1/(\log k)^c</math> for some <math>c\in (0,1)</math>

#* <math>\exp((\log \log \log k)^c)/\log k</math> for <math>c\in (0,1)</math>

# Linear up to [[polylogarithmic]] factor; <math>n=\text{poly}(\log k)*k</math>

TheThese firsthave and second haveboth been achieved, even with constant query complexity and a binary [[Alphabet (computer science)|alphabet]], such as with <math>n=k^{1+1/(\log k)^c}</math> for any <math>c\in (0,1)</math>, but there have yet to be seen any linearly testable codes of size even the third nearly linear function.<ref name=shortLTC/>

The next nearly linear goal is linear up to a [[polylogarithmic]] factor; <math>n=\text{poly}(\log k)*k</math>. Nobody has yet to come up with a linearly testable code that satisfies this constraint.<ref name=shortLTC/>

== Parallels ==

Locally testable codes have a lot in common with [[Probabilisticallyprobabilistically checkable proofs]] (PCPs). This should be apparent from the similarities of their construction. In both, we are given <math>q</math> random nonadaptive queries into a large string and if we want to accept, we must with probability 1, and if not, we must accept no more than half the time. The major difference is that PCPs are interested in accepting <math>x</math> if there exists a <math>w</math> so that <math>M^w(x)=1</math>. Locally testable codes, on the other hand, accept <math>w</math> if it is part of the code. Many things can go wrong in assuming a PCP proof encodes a locally testable code. For example, the PCP definition says nothing about invalid proofs, only invalid inputs.

Despite this difference, locally testable codes and PCPs are similar enough that frequently to construct one, a prover will construct the other along the way.<ref name=LTCandPCP>{{cite web|url=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.91.9955&rep=rep1&type=pdf|title=Locally Testable Codes|author=Mahdi Cheraghchi-Bashi-Astaneh}}</ref>

Line 38:

=== Hadamard code ===

One of the most famous error-correcting codes, the [[Hadamard code]] is a locally testable code. A codeword x is encoded in the Hadamard code to be the linear function <math>f(y)={\sum_i {x_i y_i}}</math> (mod 2). This requires listing out the result of this function for every possible y, which requires exponentially more bits than its input. To test if a string w is a codeword of the Hadamard code, all we have to do is test if the function it encodes is linear. This means simply checking if <math>w(x)\oplus w(y)=w(x\oplus y)</math> for x and y [[Uniform distribution (discrete)|uniformly random]] vectors (where <math>\oplus</math> denotes [[bitwise XOR]]).

It is easy to see that for any valid encoding <math>w</math>, this equation is true, as that is the definition of a linear function. Somewhat harder, however, is showing that a string that is <math>\delta</math>-far from C will have an upper bound on its error in terms of <math>\delta</math>. One bound is found by the direct approach of approximating the chances of exactly one of the three probes yielding an incorrect result. Let A, B, and C be the events of <math>w(x)</math>, <math>w(y)</math>, and <math>w(x\oplus y)</math> being incorrect. Let E be the event of exactly one of these occurring. This comes out to