Relations between communication complexity classes (Q751811)

The communication complexity of a Boolean function f equals the number of bits which have to be exchanged between two processors each knowing some part of the input x in order to compute f(x). This nonuniform complexity measure has found a lot of applications in complexity theory, e.g. in distributed computing, lower bounds for the VLSI complexity or monotone circuits. This paper is a major step in building a complexity theory on this complexity measure. Hence, a large number of results are proved. For most of the closure properties it is decided whether they are fulfilled. Perhaps even more important are hierarchy results, i.e. the result that a Boolean hierarchy does not collapse. Within these hierarchies also probabilistic complexity classes like the class C-BPP, the communication complexity counterpart of BPP, are investigated.