Communication Complexity And Linearly Ordered Sets

Mieczysław Kula; Małgorzata Serwecińska

Annales Mathematicae Silesianae (2015)

  • Volume: 29, Issue: 1, page 93-117
  • ISSN: 0860-2107

Abstract

top
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.

How to cite

top

Mieczysław Kula, and Małgorzata Serwecińska. "Communication Complexity And Linearly Ordered Sets." Annales Mathematicae Silesianae 29.1 (2015): 93-117. <http://eudml.org/doc/276904>.

@article{MieczysławKula2015,
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 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.},
author = {Mieczysław Kula, Małgorzata Serwecińska},
journal = {Annales Mathematicae Silesianae},
keywords = {communication complexity; linear lattice; communication protocol; interval protocol},
language = {eng},
number = {1},
pages = {93-117},
title = {Communication Complexity And Linearly Ordered Sets},
url = {http://eudml.org/doc/276904},
volume = {29},
year = {2015},
}

TY - JOUR
AU - Mieczysław Kula
AU - Małgorzata Serwecińska
TI - Communication Complexity And Linearly Ordered Sets
JO - Annales Mathematicae Silesianae
PY - 2015
VL - 29
IS - 1
SP - 93
EP - 117
AB - 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.
LA - eng
KW - communication complexity; linear lattice; communication protocol; interval protocol
UR - http://eudml.org/doc/276904
ER -

References

top
  1. [1] Ahlswede R., Cai N., Tamm U., Communication complexity in lattices, Appl. Math. Lett. 6 (1993), no. 6, 53–58.[Crossref] Zbl0791.94001
  2. [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. [3] Björner A., Kalander J., Lindström B., Communication complexity of two decision problems, Discrete Appl. Math. 39 (1992), 161–163. Zbl0769.68042
  4. [4] Kushilevitz E., Nisan N., Communication complexity, Cambridge University Press, Cambridge, 1997. Zbl0869.68048
  5. [5] Lovasz L., Sachs M., Communication complexity and combinatorial lattice theory, J. Comput. System Sci. 47 (1993), 322–349. Zbl0791.68083
  6. [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. [7] Serwecińska M., Communication complexity in linear ordered sets, Bull. Sect. Logic 33 (2004), no. 4, 209–222. Zbl1096.68071
  8. [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. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.