Communication complexity hierarchy (Q1090456)

Communication complexity of languages, defined by \textit{Ch. Papadimitriou} and \textit{M. Sipser} [J. Comput. Syst. Sci. 28, 260-269 (1984; Zbl 0584.68064)] is a tool for proving lower bounds on the area complexity and on the area-time squared complexity of VLSI circuits recognizing these languages. The abstract communication complexity model and its basic properties are investigated. A hierarchy is established with respect to the communication complexity for both deterministic and nondeterministic models. (Note that some stronger hierarchies were obtained by \textit{P. Ďuriš}, \textit{Z. Galil } and \textit{G. Schnitger} [Inf. Comput. 73, 1-22 (1987)].) A new type of communication complexity model called counterbalanced is introduced and compared with the one-way communication complexity model according to their computational powers.