Class Description

⊕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).

Linked From

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.

More about...


ZPPcc: Communication Complexity ZPP

Equals Pcc if defined in terms of total functions; is not contained in ⊕Pcc if defined in terms of partial functions [GPW16b].

More about...