99-28   Berichtsreihe des Mathematischen Seminars der Universität Kiel

Benjamin Doerr:

Communication Complexity and the Protocol Partition Number

In this article we investigate the connection between the communication complexity $D(f)$ of a function $f: X \times Y \to Z$ and its protocol partition number $C^P(f)$. Using a new tree transformation we improve the current best upper bound of $D(f) \le 3 \log_2 C^P(f)$ to $D(f) \le 2.223 \log_2 C^P(f)$. We also give a class of function $(f_n)_{n \in \N}$ showing a non-constant gap between the trivial lower bound $\log_2 C^P(f)$ and $D(f)$.

Mathematics Subject Classification (1991): 94A05

Keywords: communication complexity, protocol partition number

Mail an Jens Burmeister
[Thu Feb 19 18:56:35 2009]
Impressum