Technical Reports


Display by Author:
A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z
Search by for:

TR-237-89
On Bounded Round Multi-Prover Interactive Proof Systems
Authors: Cai, Jin-Yi, Condon, Anne, Lipton, Richard J.
Date:December 1989
Pages:16
Download Formats: [PDF]
Abstract:
We compare bounded round multi-prover interactive proof systems (MIPs) with unbounded round interactive proof systems (IPSes). We show that for any constant epsilon, any language accepted by an unbounded round IPS has a bounded round, 2-prover MIP that has error probability epsilon, resolving an open problem of Fortnow, Rompel and Sipser. To obtain this result, we show that a certain 1-round MIP that simulates the computation of an unbounded round IPS can be executed many times in parallel to significantly reduce its probability of error.