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.