Protocol partition number and deterministic communication complexity

Question

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$?

References:

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

Answer 1

Ok, so let me try to prove that two is enough, that is $cc(R)\le 2\log_2(pp(R))$. Sorry but sometimes I write leaves instead of number of leaves/pp(R), whenever the number is smaller than 1, I obviously mean this. Also, I usually write < instead of $\le$ to enhance non-tex readability.

Indirect suppose that there is an R for which this is not true and let us take the R with the smallest possible pp(R) that violates the inequality. We basically have to show that using two bits, we can halve the number of leaves in all four outcomes of the protocol tree, then we are done using induction.

Denote the possible set of inputs of Alice by X and of Bob by Y. Take the center of the protocol tree that achieves pp(R) leaves, i.e. the node deleting which the tree falls into three parts, each having at most 1/2 of the pp(R) leaves, and denote the corresponding inputs by X0 and Y0. Without loss of generality we can suppose that Alice speaks at the center and she tells whether her input belongs to XL or XR, whose disjoint union is X0. Denote the ratio of the leaves to pp(R) in XL $\times$ Y0 by L, in XR $\times$ Y0 by R and in the rest by D. Now we divide the rest into three more parts, similarly to Doerr, denoting the leaves whose rectangle intersect Y0 $\times$ X by A, whose rectangle intersect X0 $\times$ Y by B and the rest by C. Notice that A+B+C=D.

Now we know that L+R>1/2, L,R<1/2 and without loss of generality we can suppose that L is at most R. We also know D=A+B+C<1/2. It follows that 2L+A+B<1, from which we know that either L+A<1/2 or L+B<1/2, these will be our two cases.

Case L+A<1/2: First Bob tells whether his input belongs to Y0 or not. If not, we have at most D<1/2 leaves left. If it does, then Alice tells whether her input belongs to XR or not. If not, we have at most L+A<1/2 leaves left. If it does, then we have R<1/2 leaves left.

Case L+B<1/2: First Alice tells whether her input belongs to XR or not. If it does, then Bob tells whether his belongs to Y0 or not, depending on this we have R or B leaves remaining. If the input of Alice is not in XR, then Alice tells whether her input is in XL or not. If it is, then we have L+B<1/2 leaves remaining. If not, we have at most D<1/2 leaves remaining.

In all cases we are done. Let me know what you think.

Answer 2

In addition to domotorp's excellent answer giving $c\le 2$, let me mention that the recent monograph of Jukna (2012) provides an in-depth discussion of this question in Chapter 6.1. According to Jukna, the current best bound is $c \le 1.73$ by Khrapchenko (1978).

References

Stasys Jukna. Boolean Function Complexity: Advances and Frontiers. Springer, 2012.

V. M. Khrapchenko. On a relation between the complexity and the depth. Metody Diskretnogo Analiza in Synthezis of Control Systems 32: 76–94, 1978.