Class Description

UPPcc: Unrestricted Communication Analogue of PP

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].

Does not contain PHcc [RS10].

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.

Linked From

⊕Pcc: Communication Complexity ⊕P

Is not contained in UPPcc [For02].

Does not contain ZPPcc if partial functions are allowed [GPW16b].

The complexity measure associated with ⊕Pcc is equivalent to the log of the rank of the communication matrix over GF(2).

More about...


PPcc: Communication Complexity PP

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.

More about...


UPostBPPcc: Unrestricted Communication Analogue of PostBPP

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.

More about...


USBPcc: Unrestricted Communication Analogue of SBP

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].

More about...


UWAPPcc: Unrestricted Communication Analogue of WAPP

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].

More about...