The polynomial hierarchy for communication complexity, naturally built with NPcc and coNPcc forming the first level. Specifically, a cost-k protocol in the PHcc model corresponds to a constant-depth 2k-ary tree whose internal nodes are alternating layers of AND and OR gates, and whose leaves represent (the indicator functions of) either rectangles or complements of rectangles, as appropriate.
It is unknown whether Σ2cc equals Π2cc.
Defined in [BFS86], where it was also shown (among other things) that BPPcc is contained in Σ2cc ∩ Π2cc.
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 that may output 0, 1, or "abort", such that on every input, the non-abort probability is at least some α>0 (which is to be thought of as a function of n), and conditioned on not aborting, the output is correct with probability at least 2/3. The cost of a protocol is defined to be its communication cost plus log(1/α).
Contained in, but does not equal, PPcc [Kla03].
Contained in PHcc.
The complexity measure corresponding to PostBPPcc is equivalent to the "extended discrepancy bound" [GL14].
This class is not defined in terms of space, but rather by analogy with the characterization PSPACE=AP. Specifically, a protocol corresponds to a boolean formula where each leaf represents (the indicator function of) a rectangle; the cost of a protocol is the log of the size of the formula.
Contains PHcc.
Defined by [BFS86], UPPcc is one of two communication complexity analogues of PP.UPPcc is the class of all functions that are computable by polylogarithmic protocols using private (but no public) randomness, which accept with probability strictly greater than 1/2 when and accept with probably strictly less than 1/2 otherwise. No accounting is made for how many random bits are consulted during the protocol.
Does not contain ⊕Pcc [For02].
The complexity measure associated with UPPcc is equivalent to the log of the sign-rank of the communication matrix (assuming the latter has {1,-1} entries) [PS86].
See also: PPcc.
