Goldreich, OdedVadhan, SalilWigderson, Avi2009-07-302002Goldreich, Oded, Salil Vadhan, and Avi Wigderson. 2002. On interactive proofs with a laconic prover. Computational Complexity 11:1-53.1420-89541016-3328http://nrs.harvard.edu/urn-3:HUL.InstRepos:3202520We continue the investigation of interactive proofs with bounded communication, as initiated by Goldreich & Håstad (1998). Let <i>L</i> be a language that has an interactive proof in which the prover sends few (say <i>b</i>) bits to the verifier. We prove that the complement $\bar L$ has a <i>constant-round</i> interactive proof of complexity that depends only exponentially on <i>b</i>. This provides the first evidence that for <b>NP</b>-complete languages, we cannot expect interactive provers to be much more "laconic" than the standard <b>NP</b> 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$.en-USgame theorystatistical zero-knowledgesampling protocolsNPArthur-Merlin gamesinteractive proof systems10.1007/s00037-002-0169-0