Next: On the Circuit Complexity
Up: Sabbatical at MIT (1996-1998)
Previous: Property Testing and its
This paper establishes a separation between interactive proofs
and arguments, by showing that interactive proofs are unlikely
to be as efficient as arguments. The paper contains results
regarding various restrictions on the interactive proofs.
Comments:
Authored by O. Goldreich and J. Hastad. Appeared in
- IPL, Vol. 67 (4), pages 205-214, 1998.
Oded Goldreich
2003-07-30