On Interactive Proofs with a Laconic Prover
Oded Goldreich, Salil Vadhan, and Avi Wigderson
Abstract
We continue the investigation of interactive proofs with bounded communication,
as initiated by Goldreich and Håstad (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 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 (e.g. when b=1, or
when we have perfect completeness), we get significantly better upper bounds
on the complexity of $\bar L$.
Versions
-
Automata, Languages, and Programming - 28th International Colloquium,
vol. 2076 of Lecture Notes for Computer Science, pp. 334-345, Crete,
Greece, July 7-11, 2001. Springer-Verlag.
-
Electronic Colloquium on Computational Complexity TR01-046, July
2, 2001.
-
Computational Complexity 11, pages 1-53, 2002. [postscript][pdf][official
CC page]
[
back to Salil Vadhan's research interests ]