Class Description

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

Linked From

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

More about...