Relations between communication complexity classes
Bernd Halstenberg, R. Reischuk · 1988
The complexity of communication between two processors is studied in terms of complexity classes. Previously published results showing some analogies between Turing machine classes and the corresponding communication complexity classes are enlarged, and some proper inclusions are shown. The nonuniformity of communication protocols is used to show that the Boolean communication hierarchy does not collapse. For completeness an overview on communication complexity classes is added with proofs of some properties already observed by other authors.>