ECCC-Report TR01-046https://eccc.weizmann.ac.il/report/2001/046Comments and Revisions published for TR01-046en-usMon, 02 Jul 2001 09:44:22 +0300
Paper TR01-046
| On Interactive Proofs with a Laconic Prover |
Oded Goldreich,
Salil Vadhan,
Avi Wigderson
https://eccc.weizmann.ac.il/report/2001/046
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$.
Mon, 02 Jul 2001 09:44:22 +0300https://eccc.weizmann.ac.il/report/2001/046