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 constantround interactive
proof of complexity that depends only exponentially on b. This provides
the first evidence that for NPcomplete 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. 334345, Crete,
Greece, July 711, 2001. SpringerVerlag.

Electronic Colloquium on Computational Complexity TR01046, July
2, 2001.

Computational Complexity 11, pages 153, 2002. [postscript][pdf][official
CC page]
[
back to Salil Vadhan's research interests ]