On bounded round multiprover interactive proof systems
- 4 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
Bounded round multiprover interactive proof systems (MIPs) are compared with unbounded round interactive proof systems (IPSs). It is shown that for any constant epsilon , any language accepted by an unbounded round IPS has a bounded round, two-prover MIP that has error probability epsilon , resolving an open problem of L. Fortnow et al. (1988). To obtain this result, it is shown that a certain one-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.<>Keywords
This publication has 5 references indexed in Scilit:
- On the power of multi-prover interactive protocolsTheoretical Computer Science, 1994
- On the power of interactionCombinatorica, 1990
- Multi-prover interactive proofs: how to remove intractabilityPublished by Association for Computing Machinery (ACM) ,1988
- Private coins versus public coins in interactive proof systemsPublished by Association for Computing Machinery (ACM) ,1986
- Trading group theory for randomnessPublished by Association for Computing Machinery (ACM) ,1985