A note on a problem in communication complexity

Henning Wunderlich

In this note, we prove a version of Tarui's Theorem in communication complexity, namely $P{H}^{cc}\subseteq BP\cdot P{P}^{cc}$. Consequently, every measure for $P{P}^{cc}$ leads to a me…