Next: Resettably-Sound Zero-Knowledge and its
Up: Back at Weizmann (1998-2003)
Previous: Three Theorems regarding Testing
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
- Proceedings of 28th ICALP,
Springer's LNCS 2076, pages 334-345, 2001.
Oded Goldreich
2003-07-30