Fully parallelized multi-prover protocols for NEXP-time
From MaRDI portal
Publication:1356878
DOI10.1006/jcss.1997.1238zbMath0877.68078OpenAlexW2156867528MaRDI QIDQ1356878
Publication date: 8 December 1997
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jcss.1997.1238
Related Items
On the power of multi-prover interactive protocols, The complexity of approximating a nonlinear program, Quantum multi-prover interactive proof systems with limited prior entanglement., Parallel Repetition of Two-Prover One-Round Games: An Exposition, The approximation of maximum subgraph problems, On games of incomplete information, Short Locally Testable Codes and Proofs: A Survey in Two Parts, Short Locally Testable Codes and Proofs, PSPACE is provable by two provers in one round
Cites Work
- Non-deterministic exponential time has two-prover interactive protocols
- Does co-NP have short interactive proofs ?
- PSPACE is provable by two provers in one round
- On the power of multi-prover interactive protocols
- The Knowledge Complexity of Interactive Proof Systems
- Algebraic methods for interactive proof systems
