A note on a problem in communication complexity

Abstract

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 measure for $P{H}^{cc}$, subsuming a result of Linial and Shraibman that problems with high mc-rigidity lie outside the polynomial hierarchy. By slightly changing the definition of mc-rigidity (arbitrary instead of uniform distribution), it is then evident that the class $M^{cc}$ of problems with low mc-rigidity equals $BP\cdot P{P}^{cc}$. As $BP\cdot P{P}^{cc}\subseteq PSPAC{E}^{cc}$, this rules out the possibility, that had been left open, that even polynomial space is contained in $M^{cc}$.