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.