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 192
- Downloads 0
Properties and characterizations of convex functions on time scales
In this research we deal with algebraic properties and characterizations of convex functions in the context of a time scale; this notion of convexity has been studied for some other authors but the setting of properties...
Refinements of the Hermite–Hadamard inequality in NPC global spaces
In this paper we establish different refinements and applications of the Hermite–Hadamard inequality for convex functions in the context of NPC global spaces.
Solutions and stability of generalized Kannappan’s and Van Vleck’s functional equations
We study the solutions of the integral Kannappan’s and Van Vleck’s functional equations $$∫_{S}f(xyt)dμ(t) +∫_{S}f(xσ(y)t)dμ(t) = 2f(x)f(y), x,y∈S;$$ $$∫_{S}f(xσ(y)t)dμ(t)−∫_{S}f(xyt)dμ(t) = 2f(x)f(y), x,y∈S,$$ where $...
A unique common fixed point for an infinity of set-valued maps
The main purpose of this paper is to establish some common fixed point theorems for single and set-valued maps in complete metric spaces, under contractive conditions by using minimal type commutativity and without conti...
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...