Defined in [BFS86], PPcc is one of two ways to define a communication complexity analogue of PP. In PPcc, we note that in an algorithm that uses an amount of random bits bounded by , the bias between the accept and reject probabilities can be no smaller than . Thus, in PPcc, the communication complexity is defined as the sum of the traditional communication complexity (the number of exchanged bits) and the log of the reciprocal of the worst-case (smallest) bias.
The difference between this class and UPPcc is discussed further in [BVW07], where it is shown that PPcc ⊂ UPPcc.
The complexity measure corresponding to PPcc is equivalent to the "discrepancy bound" [Kla07].
See also: UPPcc.
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].
Not contained in PPcc [BVW07].
Does not contain BPPcc if partial functions are allowed [PPS14].
Contained in UPostBPPcc.
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].
Syntactically, this has the same relationship to PostBPPcc as UPPcc does to PPcc; i.e., we only allow private (no public) randomness, and do not charge for α in the cost of a protocol.
Contains PNPcc and hence does not equal PostBPPcc since it has been shown that PNPcc is not contained in PPcc much less in PostBPPcc [BVW07].
Contained in UPPcc.
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.
Syntactically, this has the same relationship to SBPcc as UPPcc does to PPcc; i.e., we only allow private (no public) randomness, and do not charge for α in the cost of a protocol. However, it has been shown that USBPcc=SBPcc [GLM+15].
Syntactically, this has the same relationship to WAPPcc as UPPcc does to PPcc; i.e., we only allow private (no public) randomness, and do not charge for α in the cost of a protocol. However, it has been shown that UWAPPcc protocols can be efficiently simulated by WAPPcc protocols with a slightly larger ε parameter [GLM+15].
