On the power of multi-prover interactive protocols

DOI10.1016/0304-3975(94)90251-8zbMath0938.68824OpenAlexW2017899870MaRDI QIDQ1341733

Michael Sipser, Lance J. Fortnow, John Rompel

Publication date: 15 June 2000

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(94)90251-8

Mathematics Subject Classification ID

Related Items

Fast approximate probabilistically checkable proofs, Model independent approach to probabilistic models, Some recent strong inapproximability results, A note on PCP vs. MIP, Interactive Oracle Proofs, Fully parallelized multi-prover protocols for NEXP-time, Anchored Parallel Repetition for Nonlocal Games, The complexity of approximating a nonlinear program, Derandomized parallel repetition theorems for free games, Simulating BPP using a general weak random source, Checking the correctness of memories, Quantum multi-prover interactive proof systems with limited prior entanglement., Structural complexity of rational interactive proofs, Fault-tolerance and complexity (Extended abstract), Non-deterministic exponential time has two-prover interactive protocols, Unnamed Item, Short Locally Testable Codes and Proofs: A Survey in Two Parts, LWPP and WPP are not uniformly gap-definable, The Complexity of Zero Knowledge, Short Locally Testable Codes and Proofs, Interactive and probabilistic proof-checking, REMARKS ON A QUERY-BASED VARIANT OF THE PARALLEL REPETITION THEOREM, Clique is hard to approximate within \(n^{1-\epsilon}\), On Dinur’s proof of the PCP theorem, Unnamed Item, A tight parallel repetition theorem for partially simulatable interactive arguments via smooth KL-divergence, A parallel repetition theorem for entangled projection games, PSPACE has constant-round quantum interactive proof systems

Cites Work

• Unnamed Item
• Unnamed Item
• Non-deterministic exponential time has two-prover interactive protocols
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• Does co-NP have short interactive proofs ?
• Are there interactive protocols for co-NP languages?
• Optimization, approximation, and complexity classes
• On games of incomplete information
• Fully parallelized multi-prover protocols for NEXP-time
• The Knowledge Complexity of Interactive Proof Systems
• Algebraic methods for interactive proof systems
• IP = PSPACE
• Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
• Designing programs that check their work