Here, Alice and Bob collectively constitute "Arthur", and Merlin sends a message that depends on the input and all the randomness, and the cost is defined to be the bit length of Merlin's message plus the communication cost of the ensuing verification protocol between Alice and Bob. (Without loss of generality, the verification protocol consists only of checking containment in a rectangle, since Merlin could always include the transcript of the verification in his message.)
It is open to prove that there exists an explicit two-party function that is not in AMcc.
Contained in PHcc.
AMcc ∩ coAMcc is not contained in PPcc if partial functions are allowed [Kla11].
The corresponding model consists of randomized protocols such that yes-inputs are accepted with probability at least α and no-inputs are accepted with probability at most α/2 where α is to be thought of as a function of n. The cost of a protocol is defined to be its communication cost plus log(1/α).
Does not contain coNPcc [Raz92] [GW14].
Contains MAcc but does not equal it, since SBPcc is not closed under intersection [GLM+15].
Contained in AMcc and in PostBPPcc.
The complexity measure corresponding to SBPcc is equivalent to the "corruption bound" [GW14].
Similar to AMcc except that for each yes-input and each outcome of Arthur’s (i.e., Alice's and Bob's) randomness, there must be a unique proof Merlin can send that will be accepted.
Does not contain NPcc [GPW16a].
Is not contained in SBPcc [GPW16a], [GLM+15].
Is contained in PostBPPcc.
Similar to AMcc except that on each yes-input, the distribution of Merlin’s proof must leak no information about the input and moreover, this proof must be unique for each outcome of Arthur’s (i.e., Alice's and Bob's) randomness.
Unlike with other communication complexity classes, it is not known whether every function can be computed with O(n) communication in the ZAMcc model. In fact it is not even obvious that every function can be computed at all in this model, but this turns out to be the case; indeed, there is an O(2n) upper bound for every function [GPW16a].
Closely related to "private simultaneous messages" protocols in cryptography [AR16].