Content deleted Content added
m →Long code: Link to the right article for "Long code" |
better title of the section |
||
Line 28:
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/>
== Connection with probabilistically checkable proofs ==
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.
| |||