Communication complexity and linearly ordered sets

Mieczysław Kula; Małgorzata Serwecińska

Published: 2015-09-30

Vol. 29 (2015)

Communication complexity and linearly ordered sets

Mieczysław Kula , Małgorzata Serwecińska

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 ????(log₂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.

Keywords:

communication complexity , linear lattice , communication protocol , interval protocol

Download files

PDF

Citation rules

Kula, M., & Serwecińska, M. (2015). Communication complexity and linearly ordered sets. Annales Mathematicae Silesianae, 29, 93–117. Retrieved from https://journals.us.edu.pl/index.php/AMSIL/article/view/13980

Similar Articles

Y. L. Tenkeu Jeufack, E. R. Alomo Temgoua, O. A. Heubo-Kwegna, Closure operations on Intuitionistic Linear algebras , Annales Mathematicae Silesianae: Vol. 38 No. 2 (2024)
Andrzej Sładek, Linear dependence of powers of linear forms , Annales Mathematicae Silesianae: Vol. 29 (2015)
Władysław Kierat, On a certain extensions of linear spaces with an algebraic derivation , Annales Mathematicae Silesianae: Vol. 1 (1985)
Jan Ligęza, The distributional solutions of some systems of linear differential equations , Annales Mathematicae Silesianae: Vol. 3 (1990)
Hoger Ghahramani, Saman Sattari, Left derivable maps at non-trivial idempotents on nest algebras , Annales Mathematicae Silesianae: Vol. 33 (2019)
Milan Tvrdý, Linear boundary value problems for generalized differential equations , Annales Mathematicae Silesianae: Vol. 14 (2000)
Andrzej Kamiński, On axioms of convergence in linear spaces , Annales Mathematicae Silesianae: Vol. 1 (1985)
Harald Fripertinger, On iteration of bijective functions with discontinuities , Annales Mathematicae Silesianae: Vol. 34 No. 1 (2020)
Jan Ligęza, On a two point boundary value problem for linear differential equations of the fourth order in the colombeau algebra , Annales Mathematicae Silesianae: Vol. 15 (2001)
Zbigniew Gajda, A characterization of functions with dense graph in the plane or half-plane , Annales Mathematicae Silesianae: Vol. 2 (1986)

1 2 3 4 5 6 > >>

You may also start an advanced similarity search for this article.

References

1. Ahlswede R., Cai N., Tamm U., Communication complexity in lattices, Appl. Math. Lett. 6 (1993), no. 6, 53–58.
2. Babaioff M., Blumrosen L., Naor M., Schapira M., Informational overhead of incentive compatibility, in: Proc. 9th ACM Conference on Electronic Commerce, ACM, 2008, pp. 88–97.
3. Björner A., Kalander J., Lindström B., Communication complexity of two decision problems, Discrete Appl. Math. 39 (1992), 161–163.
4. Kushilevitz E., Nisan N., Communication complexity, Cambridge University Press, Cambridge, 1997.
5. Lovasz L., Sachs M., Communication complexity and combinatorial lattice theory, J. Comput. System Sci. 47 (1993), 322–349.
6. Mehlhorn K., Schmidt E., Las Vegas is better than determinism in VLSI and distributed computing, in: Proc. 14th Ann. ACM Symp. on Theory of Computing, ACM, 1982, pp. 330–337.
7. Serwecińska M., Communication complexity in linear ordered sets, Bull. Sect. Logic 33 (2004), no. 4, 209–222.
8. Yao A.C., Some complexity questions related to distributive computing, in: Proc. 11th Ann. ACM Symp. on Theory of Computing, ACM, 1979, pp. 209–213. Google Scholar

Mieczysław Kula

mkula@us.edu.pl

Affiliation:

Instytut Matematyki, Uniwersytet Śląski w Katowicach Poland

Małgorzata Serwecińska

Affiliation:

Instytut Matematyki, Uniwersytet Śląski w Katowicach Poland

Vol. 29 (2015)
Published: 2015-09-30

ISSN: 0860-2107

eISSN: 2391-4238

10.1515/amsil

Publisher

University of Silesia Press

Submit