TIME: 1:30-2:20 pm,  May 8, 2007

PLACE: CSE 403

SPEAKER: Yael Taumann Kalai
         Microsoft Research and Georgia Tech

TITLE:  Interactive PCP

ABSTRACT:
A central line of research, in the area of Polynomial-time Checkable
Proofs (PCPs), is devoted to constructing short PCPs.  In this paper,
we show that if we allow an additional very short interactive phase,
then for some NP languages, one can construct PCPs that are
significantly shorter than the known (non-interactive) PCPs for
these languages.  We give several cryptographic applications for
these results.

More specifically, an *interactive-PCP* (say, for the membership in L)
is a proof that can be verified by reading only one of its bits, with
the help of a very short interactive-proof.  We show that for
membership in some languages L, there are interactive-PCPs that are
significantly shorter than the known (non-interactive) PCPs for these
languages.

Our main result is that the satisfiability of a constant depth Boolean
formula Phi(z_1,...,z_k) of size n (over the gates AND, OR, XOR, NOT)
can be proved by an interactive-PCP of size poly(k), followed by
a short interactive proof of communication complexity polylog(n).
That is, we obtain interactive-PCPs of size polynomial in the size of
the witness.  This compares to the known (non-interactive) PCPs that
are of size polynomial in the size of the instance.
By reductions, this result extends to many other central NP languages
(e.g., SAT, k-clique, Vertex-Cover, etc.).

We give many cryptographic applications and motivations for our
results. In particular, we show the following:

(1)   The satisfiability of a constant depth formula Phi(z_1,...,z_k) of
size n (as above) has an interactive zero-knowledge *proof* of 
communication complexity poly(k) (rather than poly(n)). As before, this
result extends to many other central NP languages. 

(2)  Alice can commit to a Boolean formula C of size m, by a message of
size poly(m), and later on prove to Bob any N statements of the form
C(x_1)=z_1,...,C(x_N)=z_N by a zero-knowledge *proof* of communication
complexity poly(m, log N).  Moreover, if C is a constant depth Boolean
formula then the zero-knowledge proof has communication complexity
poly(log m, log N)  (surprisingly, the communication complexity
here is significantly shorter than the size of C).

This is joint work with Ran Raz.