Locally testable code: Difference between revisions

Revision as of 13:41, 14 January 2014

Revision as of 21:04, 19 May 2014

Line 33:

Locally testable codes have a lot in common with [[probabilistically 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>

== Examples ==