Protocol partition number and deterministic communication complexity

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.
• I didn't knew about the second reference, and I tried to google it and did not find an online version. Do you have a link? Jan 14, 2011 at 5:35
• is this the author's home page? mpi-inf.mpg.de/~doerr Jan 14, 2011 at 6:12
• Yes, this is the author's homepage. The citeseerX link I used to download the paper seems to be gone. You can ask at your library if they can get a hardcopy; but It may be best to ask the author whether he is willing to put it on his homepage, or on arxiv. Jan 14, 2011 at 7:33
• The only recent thing that might be useful that I know of is this paper lab2.kuis.kyoto-u.ac.jp/~kenya/MFCS2010.pdf. Jan 15, 2011 at 13:45
• I really do not understand what you are offering the bounty for. You want a smaller constant instead of 3? You cite the Doerr paper yourself where it is improved to 2.223... Oct 28, 2011 at 5:13

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.

• Thanks a lot for this great answer! It features a good understanding of the problem, as well as originality and effort. I find your proof convincing after a first reading. It took me a moment to understand how you get $2L+A+B \le 1$; but this is clearly implied by knowing that $L+R+A+B+C=1$, and knowing of course $C \ge 0$, and by assuming $L\le R$. Nov 1, 2011 at 22:14

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.

• This chapter is about Formulas and not Communication Complexity, but the proofs indeed look similar. Are these problems equivalent? Jun 10, 2012 at 15:46
• Yes, these problems are equivalent. The proof is via Karchmer-Wigderson-games. See e.g. Theorem 3.13 in Jukna's book. (Notice that the equivalence holds for DeMorgan formulas, not for general boolean formulas over the full basis.) Jun 10, 2012 at 17:57
• In KW games the goal is to find a different coordinate if the promise is that f(x) differs from f(y), so it is quite different from communication complexity in general. Jun 10, 2012 at 20:06