Fully parallelized multi-prover protocols for NEXP-time

DOI10.1006/JCSS.1997.1238MaRDI QIDQ1356878zbMATH OpenOpenAlexFDO

Authors Dror Lapidot, Adi Shamir

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

zbMATH Keywords

multi-prover interactive proofs

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• On the power of multi-prover interactive protocols
• scientific article; zbMATH DE number 176551
• Non-deterministic exponential time has two-prover interactive protocols

Cites work

• Algebraic methods for interactive proof systems
• Does co-NP have short interactive proofs ?
• Non-deterministic exponential time has two-prover interactive protocols
• On the power of multi-prover interactive protocols
• PSPACE is provable by two provers in one round
• The Knowledge Complexity of Interactive Proof Systems

Cited in

(10)

• On the power of multi-prover interactive protocols
• Parallel repetition of two-prover one-round games: an exposition
• Short locally testable codes and proofs: a survey in two parts
• scientific article; zbMATH DE number 176551 (Why is no real title available?)
• Quantum multi-prover interactive proof systems with limited prior entanglement.
• The complexity of approximating a nonlinear program
• Short locally testable codes and proofs
• The approximation of maximum subgraph problems
• PSPACE is provable by two provers in one round
• On games of incomplete information

This page was built for publication: Fully parallelized multi-prover protocols for NEXP-time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1356878)