Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR01-046 | 2nd July 2001 00:00

#### On Interactive Proofs with a Laconic Prover

TR01-046
Authors: Oded Goldreich, Salil Vadhan, Avi Wigderson
Publication: 2nd July 2001 09:44
Keywords:

Abstract:

We continue the investigation of interactive proofs with bounded
communication, as initiated by Goldreich and Hastad (IPL 1998).
Let $L$ be a language that has an interactive proof in which the prover
sends few (say $b$) bits to the verifier.
We prove that the complement $\bar L$ has a {\em constant-round}
interactive proof of complexity that depends only exponentially on $b$.
This provides the first evidence
that for $\NP$-complete languages, we cannot
expect interactive provers to be much more
laconic'' than the standard $\NP$ proof.

When the proof system is further restricted (eg when $b=1$,
or when we have perfect completeness), we get significantly better
upper bounds on the complexity of $\bar L$.

ISSN 1433-8092 | Imprint