Lower bounds on communication complexity (Q1097691)

Communication complexity measures the amount of information which must be exchanged between two or more processors which must evaluate one or more functions for some input defined by a sequence of bits which has been distributed among them. This measure has the unusual feature that it is inherently bounded: if the input consists of n bits exchanging less than n bits will suffice since we can transmit all bits to one processor and this processor then can complete the computation by itself. As a consequence the whole research on communication complexity involving upper and lower bounds for various modes of computations and specific problems takes place within the interval O(1) - O(n). The model arose around 1980 out of the theory of VLSI design, where the input is supposed to be divided into two parts by a suitable chosen line dissecting the chip-area; the communication complexity then measures the amount of information which has to pass this dividing line, and in this way it produces a lower bound on the product of the time and the length of the separating line. In the present paper the authors have provided us with a few new sophisticated strengthenings of the theory on communication complexity (1 and 4 answer questions by Papadimitriou and Sipser): 1) They show that there are concrete examples of problems which show an exponential gap in communication complexity between k-1 round and k round in the bounded round model (communication has to proceed in interactive rounds, the number of which is restricted). 2) An even larger exponential gap is established for the same separation: however the problem instance is exhibited by an existency proof rather than an explicit description. 3) The authors show that lower bounds for the bounded-round fixed- partition model can be transformed into similar bounds for the model without the fixed partition restriction. 4) For arbitrary functions f(n) in the proper range it is shown that there exists problems solvable deterministically be exchanging f(n) bits which can not be solved nondeterministically exchanging f(n)-1 bits.