Fully Parallelized Multi-prover Protocols for NEXP-Time

✍ Scribed by Dror Lapidot; Adi Shamir

• Book ID: 102971699
• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 691 KB
• Volume: 54
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1006/jcss.1997.1238

✦ Synopsis

A major open problem in the theory of multi-prover interactive proofs is to characterize the languages which can be accepted by fully parallelized multi-prover protocols with an exponentially low probability of cheating. In this paper we solve this problem by proving that any language which can be accepted by a sequential multi-prover protocol can also be accepted by a single-round multi-party protocol, and thus the multi-prover round hierarchy collapses to its first level: MIP(poly)=MIP(1)=NEXP-time.