Communication Complexity and Lower Bounds on Multilective Computations

Department of Computer Science I, Algorithms and Complexity, University of Technology, Aachen, Ahornstrasse 55, 52056 Aachen, Germany; hromkovic@informatik.rwth-aachen.de.

Received: May 1998
Accepted: March 1999

Abstract

Communication complexity of two-party (multiparty) protocols has established itself as a successful method for proving lower bounds on the complexity of concrete problems for numerous computing models. While the relations between communication complexity and oblivious, semilective computations are usually transparent and the main difficulty is reduced to proving nontrivial lower bounds on the communication complexity of given computing problems, the situation essentially changes, if one considers non-oblivious or multilective computations. The known lower bound proofs for such computations are far from being transparent and the crucial ideas of these proofs are often hidden behind some nontrivial combinatorial analysis. The aim of this paper is to create a general framework for the use of two-party communication protocols for lower bound proofs on multilective computations. The result of this creation is not only a transparent presentation of some known lower bounds on the complexity of multilective computations on distinct computing models, but also the derivation of new nontrivial lower bounds on multilective VLSI circuits and multilective planar Boolean circuits. In the case of VLSI circuits we obtain a generalization of Thompson's lower bounds on AT² complexity for multilective circuits. The Ω(n²) lower bound on the number of gates of any k-multilective planar Boolean circuit computing a specific Boolean function of n variables is established for . Another advantage of this framework is that it provides lower bounds for a lot of concrete functions. This contrasts to the typical papers devoted to lower bound proofs, where one establishes a lower bound for one or a few specific functions.