Communication Complexity; A Survey

Abstract:

The basic question in communication complexity theory is to find the minimum number of bits two processors have to communicate in order to find the value of a 2-variable function, if one knows the value of the first variable and the other knows the value of the second. This paper surveys some basic and recent results in this theory. The connections with VLSI are sketched. There are general lower and upper bounds involving the rank of the associated matrix and non-determinism. A recent upper bound by M. Saks and the author, extending an important result of Aho, Ullman and Yannakakis is presented. Using this, it is shown that for a large class of communication complexity problems, the
square of the linear algebra lower bound on the communication complexity is an upper bound. The so-called Moebius function of lattices plays an important role. Further areas surveyed are randomized protocols and the applications of communication complexity in the other areas of complexity theory.