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 185
- Downloads 0
Some problems in the Calculus of Variations
We present some results and open problems in the Calculus of Variations.
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...
Characterizations of rotundity and smoothness by approximate orthogonalities
In this paper we consider the approximate orthogonalities in real normed spaces. Using the notion of approximate orthogonalities in real normed spaces, we provide some new characterizations of rotundity and smoothness of...
Numerical solution of time fractional Schrödinger equation by using quadratic B-spline finite elements
In this article, quadratic B-spline Galerkin method has been employed to solve the time fractional order Schrödinger equation. Numerical solutions and error norms $L_2$ and $L_∞$ are presented in tables.
Mathematical models for dynamics of molecular processes in living biological cells. A single particle tracking approach
In this survey paper we present a systematic methodology of how to identify origins of fractional dynamics. We consider three models leading to it, namely fractional Brownian motion (FBM), fractional Lévy stable motion (...