Locally Testable Codes and PCPs of Almost-Linear Length

Webpage for a paper by Oded Goldreich and Madhu Sudan


Locally testable codes are error-correcting codes that admit very efficient codeword tests. Specifically, using a constant number of (random) queries, non-codewords are rejected with probability proportional to their distance from the code. Locally testable codes are believed to be the combinatorial core of PCPs. However, the relation is less immediate than commonly believed. Nevertheless, we show that certain PCP systems can be modified to yield locally testable codes. On the other hand, we adapt techniques we develop for the construction of the latter to yield new PCPs. Our main results are locally testable codes and PCPs of almost-linear length. Specifically, we present: The novel techniques in use include a random projection of certain codewords and PCP-oracles, an adaptation of PCP constructions to obtain ``linear PCP-oracles'' for proving conjunctions of linear conditions, and a direct construction of locally testable (linear) codes of sub-exponential length.

Material available on-line

Errata: In Def. 5.7, strong soundness should be defined such that the verifier rejects with probability $\Omega(\delta(x,\pi))$, where
$$\delta(x,\pi)=\min_{x'}\{\max(\frac{\Delta(x,x')}{|x|}\;;\; \frac{\Delta(\pi,P(x'))}{\ell(|x|)})\}$$
That is, the minimization is solely over $x'$, and the relevant distances are the between $x$ and $x'$ and between $\pi$ and $P(x')$. (Compare Def. 5.9, which is a special case.) See revision May 2013. [Error pointed out by Ron Rothblum, May 2013]

Back to either Oded Goldreich's homepage. or general list of papers.