TR02-050 Authors: Oded Goldreich, Madhu Sudan

Publication: 5th August 2002 17:11

Downloads: 3865

Keywords:

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.