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 173
- Downloads 0
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.
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.
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.
Universally Kuratowski–Ulam spaces and open-open games
We examine the class of spaces in which the second player has a winning strategy in the open-open game. We show that this spaces are not universally Kuratowski–Ulam. We also show that the games $G$ and $G_7$ introduced b...
An infinite natural product
We study a countably infinite iteration of the natural product between ordinals. We present an “effective” way to compute this countable natural product; in the non trivial cases the result depends only on the natural su...