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 167
- Downloads 0
The behaviour of weak solutions of boundary value problems for linear elliptic second order equations in unbounded cone-like domains
We investigate the behaviour of weak solutions of boundary value problems (Dirichlet, Neumann, Robin and mixed) for linear elliptic divergence second order equations in domains extending to infinity along a cone. We find...
On the continuous dependence of solutions to orthogonal additivity problem on given functions
We show that the solution to the orthogonal additivity problem in real inner product spaces depends continuously on the given function and provide an application of this fact.
Random dynamical systems with jumps and with a function type intensity
In paper [4] there are considered random dynamical systems with randomly chosen jumps acting on Polish spaces. The intensity of this process is a constant $\lambda$. In this paper we formulate criteria for the existence...
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...
Report of Meeting. The Eighteenth Debrecen–Katowice Winter Seminar on Functional Equations and Inequalities Hajdúszoboszló (Hungary), January 31–February 3, 2018
Report of Meeting. The Eighteenth Debrecen–Katowice Winter Seminar on Functional Equations and Inequalities Hajdúszoboszló (Hungary), January 31–February 3, 2018.