On Bounded Round Multi-Prover Interactive Proof Systems

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.