An interactive-PCP (say, for the membership $x \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,\ldots,z_k)$ of size $n$ (over the gates
$\wedge, \vee, \oplus, \neg $) 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.).

More generally, we show that the satisfiability of
$\bigwedge_{i=1}^n[\Phi_i(z_1,\ldots,z_k) =0]$, where each
$\Phi_i(z_1,\ldots,z_k)$ is an arithmetic formula of size $n$ (say,
over $\mathbb{GF}[2]$) that computes a polynomial of degree $d$, can
be proved by an interactive-PCP of size $\poly(k,d)$, followed by a
short interactive proof of communication complexity
$\poly(d,\log n)$.

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

The satisfiability of a constant depth formula
$\Phi(z_1,\ldots,z_k)$ of size $n$ (as above) has an interactive
zero-knowledge {\em proof} of communication complexity $\poly(k)$
(rather than $\poly(n)$)\footnote{We have learnt that a similar
result was proved independently (and more or less at the same time)
by Ishai, Kushilevitz, Ostrovsky and Sahai~\cite{IKOS}.}. As before,
this result extends to many other central NP languages. This
zero-knowledge proof has some additional desired properties that
will be elaborated on in the body of the paper.

Alice can commit to a Boolean formula $\Lambda$ of size $m$, by a
message of size $\poly(m)$, and later on prove to Bob any $N$
statements of the form $\Lambda(x_1)=z_1,\ldots,\Lambda(x_N)=z_N$ by
a zero-knowledge {\em proof} of communication complexity $\poly(m,
\log N)$. Moreover, if $\Lambda$ is a constant depth Boolean formula
then the zero-knowledge proof has communication complexity
$\poly(\log m, \log N)$. We further motivate this application in
the body of the paper.