CS Colloquium on Wednesday, Mar 24 at 11AM

Speaker: Eli Ben-Sasson (http://www.eecs.harvard.edu/~eli)
         Radcliffe Institute for Advanced Study
         at Harvard University

Title: Simple PCPs with Poly-log Rate and Poly-log Query Complexity

Place: MCS 135, 111 Cummington Street (please see
       http://cs-www.bu.edu/colloquium for directions)

Abstract:

We give constructions of PCPs of length n polylog n (with respect to
circuits of size n) that can be tested 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.

The talk will be completely self-contained and accessible to an audience
with general knowledge of computer science.

First we present a novel reduction of the (NP-complete) graph 3-coloring
problem (on a graph with n vertices) to the following one: Given oracle
access to a string of length 10 n log n, test whether it is close to being
an evaluation of some (univariate) polynomial of degree n log n.

While somewhat similar reductions have been extensively used in previous
PCP constructions, our new reduction favors over them in its simplicity.
Notice the degree of the polynomial (= n log n) is larger than the size of
the original graph (= n). Thus, testing the low degree of this string seems
to cost more queries than required for reading the original 3-coloring in
its entirety!

To overcome this, we present a short and simple proof of proximity for
Reed-Solomon codes. Namely, verifying that a string of length 2N is close
to an evaluation of a degree N polynomial can be done with polylog queries
into the string and into an additional proof of length N polylog N.

[Joint work with Madhu Sudan]

-------------------------------------------------------------------------  

Host: Azer Bestavros (http://www.cs.bu.edu/~best)