The celebrated IP=PSPACE Theorem [LFKN92,Shamir92] allows an all-powerful but untrusted prover to convince a polynomial-time verifier of the validity of extremely complicated statements (as long as they can be evaluated using polynomial space). The interactive proof system designed for this purpose requires a polynomial number of communication rounds and an exponential-time (polynomial-space complete) prover. In this paper, we study the power of more efficient interactive proof systems.

Our main result is that for every statement that can be evaluated in polynomial time and bounded-polynomial space there exists an interactive proof that satisfies the following strict efficiency requirements: (1) the honest prover runs in polynomial time, (2) the verifier is almost linear time (and under some conditions even sub linear), and (3) the interaction consists of only a constant number of communication rounds. Prior to this work, very little was known about the power of efficient, constant-round interactive proofs. This result represents significant progress on the round complexity of interactive proofs (even if we ignore the running time of the honest prover), and on the expressive power of interactive proofs with polynomial-time honest prover (even if we ignore the round complexity). This result has several applications, and in particular it can be used for verifiable delegation of computation.

Our construction leverages several new notions of interactive proofs, which may be of independent interest. One of these notions is that of unambiguous interactive proofs where the prover has a unique successful strategy. Another notion is that of probabilistically checkable interactive proofs (PCIPs) where the verifier only reads a few bits of the transcript in checking the proof (this could be viewed as an interactive extension of PCPs).

The celebrated IP=PSPACE Theorem [LFKN92,Shamir92] allows an
all-powerful but untrusted prover to convince a polynomial-time
verifier of the validity of extremely complicated statements (as
long as they can be evaluated using polynomial space). The
interactive proof system designed for this purpose requires a
polynomial number of communication rounds and an exponential-time
(polynomial-space complete) prover. In this paper, we study the
power of more efficient interactive proof systems.

Our main result is that for every statement that can be evaluated
in polynomial time and bounded-polynomial space there exists an
interactive proof that satisfies the following strict efficiency
requirements: (1) the honest prover runs in polynomial time, (2)
the verifier is almost linear time (and under some conditions
even sub linear), and (3) the interaction consists of only a
constant number of communication rounds. Prior to this work,
very little was known about the power of efficient,
constant-round interactive proofs (rather than arguments). This
result represents significant progress on the round complexity of
interactive proofs (even if we ignore the running time of the
honest prover), and on the expressive power of interactive proofs
with polynomial-time honest prover (even if we ignore the round
complexity). This result has several applications, and in
particular it can be used for verifiable delegation of
computation.

Our construction leverages several new notions of interactive
proofs, which may be of independent interest. One of these
notions is that of unambiguous interactive proofs where the
prover has a unique successful strategy. Another notion is that
of probabilistically checkable interactive proofs (PCIPs) where
the verifier only reads a few bits of the transcript in checking
the proof (this could be viewed as an interactive extension of
PCPs).

Minor changes

The celebrated IP=PSPACE Theorem [LFKN92,Shamir92] allows an all-powerful but untrusted prover to convince a polynomial-time verifier of the validity of extremely complicated statements (as long as they can be evaluated using polynomial space). The interactive proof system designed for this purpose requires a polynomial number of communication rounds and an exponential-time (polynomial-space complete) prover. In this paper, we study the power of more efficient interactive proof systems.

Our main result is that for every statement that can be evaluated in polynomial time and bounded-polynomial space there exists an interactive proof that satisfies the following strict efficiency requirements: (1) the honest prover runs in polynomial time, (2) the verifier is almost linear time (and under some conditions even sub linear), and (3) the interaction consists of only a constant number of communication rounds. Prior to this work, very little was known about the power of efficient, constant-round interactive proofs. This result represents significant progress on the round complexity of interactive proofs (even if we ignore the running time of the honest prover), and on the expressive power of interactive proofs with polynomial-time honest prover (even if we ignore the round complexity). This result has several applications, and in particular it can be used for verifiable delegation of computation.

Our construction leverages several new notions of interactive proofs, which may be of independent interest. One of these notions is that of unambiguous interactive proofs where the prover has a unique successful strategy. Another notion is that of probabilistically checkable interactive proofs (PCIPs) where the verifier only reads a few bits of the transcript in checking the proof (this could be viewed as an interactive extension of PCPs).