Pb. Miltersen et al., ON DATA-STRUCTURES AND ASYMMETRIC COMMUNICATION COMPLEXITY, Journal of computer and system sciences (Print), 57(1), 1998, pp. 37-49
Citations number
26
Categorie Soggetti
Computer Science Theory & Methods","Computer Science Hardware & Architecture","Computer Science Hardware & Architecture","Computer Science Theory & Methods
In this paper we consider two-party communication complexity, the ''as
ymmetric case'', when the input sizes of the two players differ signif
icantly. Most of previous work on communication complexity only consid
ers the total number of bits sent, but we study trade-offs between the
number of bits the first player sends and the number of bits the seco
nd sends. These types of questions are closely related to the complexi
ty of static data structure problems in the cell probe model. We deriv
e two generally applicable methods of proving lower bounds and obtain
several applications. These applications include new lower bounds for
data structures in the cell probe model. Of particular interest is our
''round elimination'' lemma, which is interesting also for the usual
symmetric communication case. This lemma generalizes and abstracts in
a very clean form the ''round reduction'' techniques used in many prev
ious lower bound proofs. (C) 1998 Academic Press.