On Interactive Proofs with a Laconic Prover

DSpace/Manakin Repository

On Interactive Proofs with a Laconic Prover

Citable link to this page


Title: On Interactive Proofs with a Laconic Prover
Author: Vadhan, Salil; Wigderson, Avi; Goldreich, Oded

Note: Order does not necessarily reflect citation order of authors.

Citation: Goldreich, Oded, Salil Vadhan, and Avi Wigderson. 2002. On interactive proofs with a laconic prover. Computational Complexity 11:1-53.
Full Text & Related Files:
Abstract: We continue the investigation of interactive proofs with bounded communication, as initiated by Goldreich & Håstad (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$.
Published Version: http://dx.doi.org/10.1007/s00037-002-0169-0
Other Sources: http://people.seas.harvard.edu/~salil/papers/laconic-abs.html
Terms of Use: This article is made available under the terms and conditions applicable to Other Posted Material, as set forth at http://nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-use#LAA
Citable link to this page: http://nrs.harvard.edu/urn-3:HUL.InstRepos:3202520
Downloads of this work:

Show full Dublin Core record

This item appears in the following Collection(s)


Search DASH

Advanced Search