On Interactive Proofs with a Laconic Prover

Webpage for a paper by Oded Goldreich, Salil Vadhan and Avi Wigderson


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 m) 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 m. 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 m=1, or when we have perfect completeness), we get significantly better upper bounds on the complexity of bar L.

Material available on-line

Back to either Oded Goldreich's homepage. or general list of papers.