We give constructions of PCPs of length n*polylog(n) (with respect
to circuits of size n) that can be verified by making polylog(n)
queries to bits of the proof. These PCPs are not only shorter than
previous ones, but also simpler. Our (only) building blocks are
Reed-Solomon codes and the bivariate low degree test of Polischuk
and Spielman.

First, we present a new reduction from the verification of SAT to
the following verification problem. Given oracle access to a
function on a domain of size n'=n*polylog(n), verify whether it is
close to being an evaluation of a univariate polynomial of degree
n'/10. While such reductions, from SAT-verification to
verification of algebraic properties, have been extensively used
in previous PCP constructions, our new reduction favors over them
in its simplicity.

The reduction however does not seem to make the task of
SAT-verification any easier. The degree of the polynomial to be
tested is larger than the size of the original SAT problem. Thus,
testing low degree of this string seems to cost more queries than
required for reading the original satisfying assignment in its
entirety! To overcome this, we present a short ``PCP of
Proximity'' for certain Reed-Solomon codes. Specifically, we
design a verifier that makes oracle access to the function (on the
domain of size n') and an auxiliary ``proof oracle'' and accepts
polynomials of degree n'/10 (when they are accompanied with the
right auxiliary information) and rejects functions that are far
from any polynomial of degree n'/10. The verifier makes only
polylog(n') queries into two oracles (the function and the
auxiliary proof).

Using these results over appropriately chosen fields translates
our results into PCP verifiers whose query complexity is a
poly-logarithmic number of bits. Our PCPs of proximity for
Reed-Solomon codes also yields a new class of locally testable
codes with poly-logarithmic rate and query complexity.