Results on communication complexity classes

Abstract

The authors consider deterministic, probabilistic, nondeterministic, and alternating complexity classes defined by polylogarithmic communication. They give a simple technique allowing translation of most known separation and containment results for complexity classes of the fixed-partition model to the more difficult optimal partition model, for which few results were previously known. They demonstrate that a certain natural language (block equality) in Σ2 cc is also, unexpectedly, in Π2 cc.