Issue |
RAIRO-Theor. Inf. Appl.
Volume 33, Number 2, March April 1999
|
|
---|---|---|
Page(s) | 193 - 212 | |
DOI | https://doi.org/10.1051/ita:1999113 | |
Published online | 15 August 2002 |
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
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 AT2 complexity for multilective circuits.
The Ω(n2) 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.
Mathematics Subject Classification: F.2.3 / F.1.1 / G.2.1
Key words: Communication complexity / lower bounds on complexity / Boolean functions / branching programs / circuits.
© EDP Sciences, 1999
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.