Class Description

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.

Linked From

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

More about...

PP^cc: Communication Complexity PP

Defined in [BFS86], PP^cc is one of two ways to define a communication complexity analogue of PP. In PP^cc, we note that in an algorithm that uses an amount of random bits bounded by ${\displaystyle c}$, the bias between the accept and reject probabilities can be no smaller than ${\displaystyle 2^{c}}$. Thus, in PP^cc, 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 UPP^cc is discussed further in [BVW07], where it is shown that PP^cc ⊂ UPP^cc.

The complexity measure corresponding to PP^cc is equivalent to the "discrepancy bound" [Kla07].

See also: UPP^cc.

More about...

UPostBPP^cc: Unrestricted Communication Analogue of PostBPP

Syntactically, this has the same relationship to PostBPP^cc as UPP^cc does to PP^cc; i.e., we only allow private (no public) randomness, and do not charge for α in the cost of a protocol.

Contains P^NPcc and hence does not equal PostBPP^cc since it has been shown that P^NPcc is not contained in PP^cc much less in PostBPP^cc [BVW07].

Contained in UPP^cc.

More about...

USBP^cc: Unrestricted Communication Analogue of SBP

Syntactically, this has the same relationship to SBP^cc as UPP^cc does to PP^cc; 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 USBP^cc=SBP^cc [GLM+15].

More about...

UWAPP^cc: Unrestricted Communication Analogue of WAPP

Syntactically, this has the same relationship to WAPP^cc as UPP^cc does to PP^cc; 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 UWAPP^cc protocols can be efficiently simulated by WAPP^cc protocols with a slightly larger ε parameter [GLM+15].

More about...