Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR01-046 | 2nd July 2001 00:00

On Interactive Proofs with a Laconic Prover



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