## Locally Testable Codes and PCPs of Almost-Linear Length

#### Abstract

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:
• Locally testable (linear) codes in which $k$ information bits are encoded by a codeword of length approximately $k exp(sqrt(log k))$. This improves over previous results that either yield codewords of exponential length or obtained almost quadratic length codewords for sufficiently large non-binary alphabet.
• PCP systems of almost-linear length for SAT. The length of the proof is approximately $n exp(sqrt(log n))$ and verification in performed by a constant number (i.e., 19) of queries, as opposed to previous results that used proof length $exp((1+O(1/q))log n)$ for verification by $q$ queries.
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.