<abstract xmlns="http://www.w3.org/1999/xhtml"><p>The paper is devoted to the communication complexity of lattice operations in linearly ordered finite sets. All well known techniques ([4, Chapter 1]) to determine the communication complexity of the infimum function in linear lattices disappoint, because a gap between the lower and upper bound is equal to <italic>O</italic>(log<sub>2</sub><italic>n</italic>), where <italic>n</italic> is the cardinality of the lattice. Therefore our aim will be to investigate the communication complexity of the function more carefully. We consider a family of so called interval protocols and we construct the interval protocols for the infimum. We prove that the constructed protocols are optimal in the family of interval protocols. It is still open problem to compute the communication complexity of constructed protocols but the numerical experiments show that their complexity is less than the complexity of known protocols for the infimum function.</p></abstract>

The paper is devoted to the communication complexity of lattice operations in linearly ordered finite sets. All well known techniques ([4, Chapter 1]) to determine the communication complexity of the infimum function in linear lattices disappoint, because a gap between the lower and upper bound is equal to O(log2n), where n is the cardinality of the lattice. Therefore our aim will be to investigate the communication complexity of the function more carefully. We consider a family of so called interval protocols and we construct the interval protocols for the infimum. We prove that the constructed protocols are optimal in the family of interval protocols. It is still open problem to compute the communication complexity of constructed protocols but the numerical experiments show that their complexity is less than the complexity of known protocols for the infimum function.

Communication Complexity And Linearly Ordered Sets

Institute of Mathematics, University of Silesia, Bankowa 14 40-007 Katowice, Poland

Annales Mathematicae Silesianae

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

{"article-title":"Communication Complexity And Linearly Ordered Sets"}

The paper is devoted to the communication complexity of lattice operations in linearly ordered finite sets. All well known techniques ([4, Chapter 1]) to...

Communication Complexity And Linearly Ordered Sets

Online veröffentlicht: 30. Sept. 2015

Seitenbereich: 93 - 117

Eingereicht: 24. Juli 2014

DOI: https://doi.org/10.1515/amsil-2015-0008

© Mieczysław Kula et al.

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.