Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR01-046 | 2nd July 2001 00:00

On Interactive Proofs with a Laconic Prover

RSS-Feed

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