next up previous
Next: Resettably-Sound Zero-Knowledge and its Up: Back at Weizmann (1998-2003) Previous: Three Theorems regarding Testing

On interactive proofs with a laconic provers

This work provides evidence that NP-complete sets cannot have interactive provers that are much more ``laconic'' (i.e., send significantly less bits) than the standard NP-proof. Specifically, the main result in this work shows that if L has an interactive proof in which the prover sends b bits to the verifier, then the complement of L has a constant-round interactive proof of complexity that depends only exponentially on b.


Comments: Authored by O. Goldreich, S. Vadhan and A. Wigderson. Appeared in



Oded Goldreich
2003-07-30