Are there any known results on the complexity class that is MIP except with independence of provers loosened to allow "limited classical communication" between provers: where total message size sent between them is e.g. logarithmic in problem size?

Clearly we have that allowing $O(n)$-size communication just = IP = PSPACE, and disallowing communication entirely = MIP = NEXP, but with only $O(\log n)$ bits of inter-prover communication allowed one prover cannot get access to the full input of the other, and thus cannot simulate the other prover directly. On the other hand, intuitively having some ability to signal does allow the provers to conspire together.

I am aware of some related results in the quantum setting (e.g. MIP* = RE or MIP with non-signalling correlation = DEXP), but didn’t find any literature on this strictly classical case. There might also be relations to communications complexity here, in that we’re looking for the communications complexity of simulating the output of the other prover (clearly the naive n-bit approach of sending the entire input is possible, but is it possible to do better?)

Note that the related question [1] investigates limits on prover-verifier communication (with provers assumed to be independent) instead of prover-prover communication.

[1] What is known about multi-prover interactive proofs with short messages?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.