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 170
- Downloads 0
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.
Multipliers of uniform topological algebras
Let $E$ be a complete uniform topological algebra with Arens-Michael normed factors $(E_α)_{α∈Λ}$. Then $M(E)\cong\lim_{←}M(E_α)$ within an algebra isomorphism $φ$. If each factor $E_α$ is complete, then every multiplier...
Outer measures on a commutative ring induced by measures on its spectrum
On a commutative ring $R$ we study outer measures induced by measures on $Spec(R)$. The focus is on examples of such outer measures and on subsets of $R$ that satisfy the Carathéodory condition.
On orthogonally additive functions with big graphs
Let $E$ be a separable real inner product space of dimension at least 2 and $V$ be a metrizable and separable linear topological space. We show that the set of all orthogonally additive functions mapping $E$ into $V$ and...
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.