On the power of multi-power interactive protocols

descriptionPublicationkeyboard_double_arrow_right Article 01 Jan 1988Publisher:IEEEJournal:[1988] Proceedings. Structure in Complexity Theory Third Annual Conference

Authors: L. Fortnow; J. Rompel; M. Sipser;

doi: 10.1109/sct.1988.5275

On the power of multi-power interactive protocols

- Summary
- Related research
  (3)
- Metrics

Abstract

A simple characterization of the power of the multipower model in terms of probabilistic oracle Turing machines is given. It is shown that languages that have single-prover interactive protocols also have two prover-bounded round protocols and that languages that have multiprover interactive protocols have two prover protocols and three prover-bounded round protocols. An oracle is given relative to which there exists a co-NP language, that is not accepted by any multiprover interactive protocol. >

Related Organizations

Massachusetts Institute of Technology
United States

3 Research products, page 1 of 1

Perfect Zero Knowledge for Quantum Multiprover Interactive Proofs
2019IsAmongTopNSimilarDocuments
Quantum Multiprover Interactive Proofs with Communicating Provers
2014IsAmongTopNSimilarDocuments
On the complexity of zero gap MIP*
2020IsAmongTopNSimilarDocuments

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	34
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Top 10%
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Top 1%
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average