My impression is that for standard constructions of MIP ("Multiple Independent Prover") protocols, the verifiers must have shared randomness. ​ What happens if the verifiers are
also independent until the interactions have all finished? ​ (i.e., Each independent
prover interacts with a different independent verifier and then the transcripts
of the interactions get sent to the final verifier, which either accepts or rejects.)

More Formally: ​ What is known about the power of MIP protocols in which,

for each prover, the computation of what (if anything) the verifier sends
does not use anything about the partial transcripts for the other provers
the randomness strings used for the verifier's interactions
with different provers are independent of each other


By this paper, the public coin minimal-interaction version of that collapses to AM.

  • 1
    $\begingroup$ I don't understand the question. In the standard definition of MIP, there is only one verifier, and he does not share randomness with anyone. $\endgroup$ – Emil Jeřábek Apr 25 '16 at 8:44
  • 1
    $\begingroup$ Already a single prover with a single verifier and public coins can recognize all of PSPACE, so there is no way it can collapse all the way down to AM. Do you actually mean AM[poly(n)] (that is, PSPACE)? Or are the protocols implicitly restricted to a constant number of rounds? $\endgroup$ – Emil Jeřábek Apr 25 '16 at 9:03
  • $\begingroup$ I fixed the last line. ​ ​ $\endgroup$ – user6973 Apr 25 '16 at 9:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy