Communication Complexity and Lower Bounds on Multilective Computations

Issue		RAIRO-Theor. Inf. Appl. Volume 33, Number 2, March-April 1999


Page(s)		193 - 212
DOI		10.1051/ita:1999113

DOI: 10.1051/ita:1999113

Theoret. Informatics Appl. 33 (1999) 193-212

Communication Complexity and Lower Bounds on Multilective Computations

Juraj Hromkovic
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 $\Omega(n^2)$ 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 $k<\frac{1}{2} \log_2 n$ . 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.

Keywords and phrases: Communication complexity, lower bounds on complexity, Boolean functions, branching programs, circuits.

AMS Subject Classification: F.2.3., F.1.1., G.2.1.

Communicated by: I. Wegener

What is OpenURL?

The OpenURL standard is a protocol for transmission of metadata describing the resource that you wish to access. An OpenURL link contains article metadata and directs it to the OpenURL server of your choice. The OpenURL server can provide access to the resource and also offer complementary services (specific search engine, export of references...). The OpenURL link can be generated by different means.

If your librarian has set up your subscription with an OpenURL resolver, OpenURL links appear automatically on the abstract pages.
You can define your own OpenURL resolver with your EDPS Account. In this case your choice will be given priority over that of your library.
You can use an add-on for your browser (Firefox or I.E.) to display OpenURL links on a page (see http://www.openly.com/openurlref/). You should disable this module if you wish to use the OpenURL server that you or your library have defined.