Class Description

⊕P^cc: Communication Complexity ⊕P

Is not contained in UPP^cc [For02].

Does not contain ZPP^cc if partial functions are allowed [GPW16b].

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

Linked From

UPP^cc: Unrestricted Communication Analogue of PP

Defined by [BFS86], UPP^cc is one of two communication complexity analogues of PP.UPP^cc is the class of all functions ${\displaystyle f:\{0,1\}^{n}\times \{0,1\}^{n}\to \{0,1\}}$ that are computable by polylogarithmic protocols using private (but no public) randomness, which accept with probability strictly greater than 1/2 when ${\displaystyle f(x,y)=1}$ 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 ⊕P^cc [For02].

Does not contain PH^cc [RS10].

The complexity measure associated with UPP^cc is equivalent to the log of the sign-rank of the communication matrix (assuming the latter has {1,-1} entries) [PS86].

See also: PP^cc.

More about...

ZPP^cc: Communication Complexity ZPP

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

More about...