Communication Complexity And Linearly Ordered Sets

• Autorzy: Mieczysław Kula , Małgorzata Serwecińska
• Języki publikacji: EN

Abstrakty

EN

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 O(log2 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.

Słowa kluczowe

EN

communication complexity; linear lattice; communication protocol; interval protocol

Kategorie tematyczne

• 68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
• 68Q25: Analysis of algorithms and problem complexity

• Wydawca: De Gruyter Open
• Czasopismo: Annales Mathematicae Silesianae
• Rocznik: 2015
• Tom: 29
• Numer: 1
• Strony: 93-117

Daty

wydano

2015-09-01

otrzymano

2014-07-24

poprawiono

2015-03-21

online

2015-09-30

Twórcy

autor

Mieczysław Kula

• Institute of Mathematics, University of Silesia, Bankowa 14 40-007 Katowice, Poland

autor

Małgorzata Serwecińska

• Institute of Mathematics, University of Silesia, Bankowa 14 40-007 Katowice, Poland

Bibliografia

• [1] Ahlswede R., Cai N., Tamm U., Communication complexity in lattices, Appl. Math. Lett. 6 (1993), no. 6, 53–58.[Crossref]
• [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.

Identyfikatory

DOI

10.1515/amsil-2015-0008