Class Description

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

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