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