Locally Testable Codes and PCPs of Almost-Linear Length
Webpage for a paper by Oded Goldreich and Madhu Sudan
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
Back to
either Oded Goldreich's homepage.
or general list of papers.