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 150
- Downloads 0
Wild primes of a higher degree self-equivalence of a number field
Let $\mathcal{l} > 2$ be a prime number. Let $K$ be a number field containing a unique $\mathcal{l}$-adic prime and assume that its class is an $\mathcal{l}$th power in the class group $C_K$. The main theorem of the pape...
Infinite towers of Galois defect extensions of Kaplansky fields
We give conditions for Kaplansky fields to admit infinite towers of Galois defect extensions of prime degree. As proofs of the presented facts are constructive, this provides examples of constructions of infinite towers...
Complementary results to Heuvers’s characterization of logarithmic functions
Based on a characterization of logarithmic functions due to Heuvers we develop analogous results for multiplicative, exponential and additive functions, respectively.
On the general and measurable solutions of some functional equations
The general solutions of two functional equations, without imposing any regularity condition on any of the functions appearing, have been obtained. From these general solutions, the Lebesgue measurable solutions have bee...
On stability of the Cauchy functional equation in groupoids
We give some stability results for the functional equation $a(xy)=a(x)+a(y)$, where $a:G→E$, $G$ being a groupoid and $E$ a Banach space.