Besides (deterministic) communication complexity $cc(R)$ of a relation $R$, another basic measure for the amount of communication needed is the protocol partition number $pp(R)$. The relation between these two measures is known up to a constant factor. The monograph by Kushilevitz and Nisan (1997) gives
$$cc(R)/3 \le \log_2(pp(R)) \le cc(R).$$
Regarding the second inequality, it is easy to give (an infinite family of) relations $R$ with $\log_2(pp(R)) = cc(R)$.
Regarding the first inequality, Doerr (1999) showed that we can replace the factor $c=3$ in the first bound by $c=2.223$. By how much can the first bound be improved, if at all?
Additional motivation from descriptional complexity: Improving the constant $2.223$ will result in an improved lower bound on the minimum size of regular expressions equivalent to a given DFA describing some finite language, see Gruber and Johannsen (2008).
Although not directly related to this question, Kushilevitz, Linial and Ostrovsky (1999) gave relations $R$ with $cc(R)/(2-o(1)) \ge \log_2(rp(R))$, where $rp(R)$ is the rectangle partition number.
EDIT: Notice that the above question is equivalent to the following question in Boolean circuit complexity: What is the optimum constant $c$ such that every boolean DeMorgan formula of leafsize L can be transformed into an equivalent formula of depth at most $c \log_2L$?
- Kushilevitz, Eyal; Nisan, Noam: Communication Complexity. Cambridge University Press, 1997.
- Kushilevitz, Eyal; Linial, Nathan; Ostrovsky, Rafail: The Linear-Array Conjecture in Communication Complexity is False, Combinatorica 19(2):241-254, 1999.
- Doerr, Benjamin: Communication Complexity and the Protocol Partition Number, Technical Report 99-28, Berichtsreihe des Mathematischen Seminars der Universität Kiel, 1999.
- Gruber, Hermann; Johannsen, Jan: Optimal Lower Bounds on Regular Expression Size using Communication Complexity. In: Foundations of Software Science and Computation Structures 2008 (FoSSaCS 2008), LNCS 4962, 273-286. Springer.