Class Description

PostBPPcc: Communication Complexity PostBPP

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

Linked From

SBPcc: Communication Complexity SBP

The corresponding model consists of randomized protocols such that yes-inputs are accepted with probability at least α and no-inputs are accepted with probability at most α/2 where α is to be thought of as a function of n. The cost of a protocol is defined to be its communication cost plus log(1/α).

Does not contain coNPcc [Raz92] [GW14].

Contains MAcc but does not equal it, since SBPcc is not closed under intersection [GLM+15].

Contained in AMcc and in PostBPPcc.

The complexity measure corresponding to SBPcc is equivalent to the "corruption bound" [GW14].

More about...


UAMcc: Unambiguous Arthur-Merlin Communication Complexity

Similar to AMcc except that for each yes-input and each outcome of Arthur’s (i.e., Alice's and Bob's) randomness, there must be a unique proof Merlin can send that will be accepted.

Does not contain NPcc [GPW16a].

Is not contained in SBPcc [GPW16a], [GLM+15].

Is contained in PostBPPcc.

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