Technical Report CS0493

Title: Proving Properties of Interactive Proofs by a Generalized Counting Technique
Authors: L. Babai and S. Moran
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.
CopyrightThe 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 (, 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

Computer science department, Technion