On the Power of Multi-Prover Interactive Protocols

By Lance Fortnow, John Rompel, Michael Sipser. 1994

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Prio: Private, Robust, and Scalable Computation of Aggregate Statistics (2017, background): “Prior work has studied interactive proofs in both the many-prover [14,60] and many-verifier settings [1, 10].”
A threshold of ln n for approximating set cover (preliminary version) (1996, background): “Unfortunately, this is in general not true, due to subtle reasons that are best explained by explicit counterexamples [Fortnow et al. 1994].”
Robust pcps of proximity, shorter pcps and applications to coding (2004, methodology): “[14] performs less poorly than usual (i.”
Consequences and limits of nonlocal strategies (2004, background): “ for each one. The veriﬁer accepts if and only if the responses satisfy the clause. The prover’s success probability is less than one whenever the formula is unsatisﬁable. Fortnow, Rompel, and Sipser [22] showed that, with a second prover, who is sent a single randomly chosen query from those of the”
Interactive Oracle Proofs (2016, methodology): “Fortnow, Rompel, and Sipser [FRS88] show that interaction with two provers is equivalent to interaction with one prover plus oracle access to a proof string, and from there obtain that MIP [poly( n ) , poly( n )] ⊆ NEXP ; Babai, Fortnow and Lund [BFL90] show that NEXP has 1 -round 2 -prover…”
Introduction to Property Testing (2017, methodology): “The PCP model was suggested by Fortnow, Rompel, and Sipser [118] as a model capturing the power of the (related) model of multi-prover interactive proofs, which was introduced by BenOr, Goldwasser, Kilian and Wigderson [43] as a generalization of the model of interactive proofs (introduced by Goldwa”
Cooperative Provable Data Possession for Integrity Verification in Multicloud Storage (2012, background): “The CPDP construction is in essence a Multi-Prover Zeroknowledge Proof (MP-ZKP) system [11], which can be considered as an extension of the notion of an IPS.”
Randomized algorithms (1995, unknown): “These concepts are variants of the probabilistic oracle machines introduced by Fortnow, Rompel, ,and Sipser [153] as an alternate view of multiprover systems.”
The PCP theorem by gap amplification (2006, unknown): “Let us just mention that an exciting sequence of papers (see [6, 14, 5]) lead to the following theorem: the class of all languages with exponential-sized proofs is equal to the class of all languages that can be verified by a (randomized) polynomial-time verifier.”