Communication complexity and linearly ordered sets
Journal Title: Annales Mathematicae Silesianae - Year 2015, Vol 29, Issue
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 $\mathcal{O}(\log_2 n)$, 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.
Authors and Affiliations
Mieczysław Kula, Małgorzata Serwecińska
Keywords
Related Articles
- EP ID EP230407
- DOI 10.1515/amsil-2015-0008
- Views 181
- Downloads 0
A simple proof of the Polar Decomposition Theorem
In this expository paper, we present a new and easier proof of the Polar Decomposition Theorem. Unlike in classical proofs, we do not use the square root of a positive matrix. The presented proof is accessible to a broad...
A general fixed point theorem for implicit cyclic multi-valued contraction mappings
In this paper, a general fixed point theorem for cyclic multi-valued mappings satisfying an implicit relation from [19] different from implicit relations used in [13] and [23], generalizing some results from [22], [15],...
Fixed point results satisfying rational type contractive conditions in complex valued metric spaces – revisited
In our previous work titled “Fixed Point Results Satisfying Rational type Contractive Conditions in Complex Valued Metric Spaces” [Ann. Math. Sil. 30 (2016), 89–110], some errors has been made in the main results (Theore...
An application of the theory of scale of Banach spaces
The abstract Cauchy problem on scales of Banach space was considered by many authors. The goal of this paper is to show that the choice of the space on scale is significant. We prove a theorem that the selection of the s...
Linear dependence of powers of linear forms
The main goal of the paper is to examine the dimension of the vector space spanned by powers of linear forms. We also find a lower bound for the number of summands in the presentation of zero form as a sum of d-th powers...