Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR02-050 | 5th August 2002 00:00

Locally Testable Codes and PCPs of Almost-Linear Length


Authors: Oded Goldreich, Madhu Sudan
Publication: 5th August 2002 17:11
Downloads: 3731


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:

o Locally testable (linear) codes in which $k$ information bits
are encoded by a codeword of length approximately
$k\cdot\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.

o PCP systems of almost-linear length for SAT. The length of
the proof is approximately $n\cdot\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
$n^{1+O(1/q)}$ 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.

ISSN 1433-8092 | Imprint