## On Interactive Proofs with a Laconic Prover

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

#### 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 **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.