TR04-060 Authors: Eli Ben-Sasson, Madhu Sudan

Publication: 22nd July 2004 21:45

Downloads: 3672

Keywords:

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.