| TR#: | CS0493 |
| Class: | CS |
| Title: | Proving Properties of Interactive Proofs by a Generalized Counting Technique |
| Authors: | L. Babai and S. Moran |
| CS0493.pdf | |
| Abstract: | The problem of proving membership in languages accepted by interactive Proof protocols is reduced to the problem of estimating the number of leaves in certain trees. Using this reduction,. we present a direct proof that every language accepted by an interactive protocol within g(n) rounds is also accepted by an Arthur Merlin game within Upper_Bould(g(n)/2) rounds. This unifies the proofs of the two main positive results on the IP Hierarchy, namely: that private coin tossing can be replaced by public coin tossing, and that the number of interactions can be reduced by a constant factor. |
| Copyright | The above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information |
Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1988/CS/CS0493), rather than to the URL of the PDF files directly. The latter URLs may change without notice.
To the list of the CS technical reports of 1988
To the main CS technical reports page