<p>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).</p>

<p><strong>References</strong></p>

<p>Stasys Jukna. <a href="http://www.thi.informatik.uni-frankfurt.de/~jukna/boolean/q.pdf" rel="nofollow">Boolean Function Complexity: Advances and Frontiers.</a> Springer, 2012.</p>

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

CC BY-SA 3.0
2012-06-10T15:46:24.537Z
This chapter is about Formulas and not Communication Complexity, but the proofs indeed look similar. Are these problems equivalent?
domotorp
CC BY-SA 3.0
2012-06-10T17:57:55.073Z
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.)
Hermann Gruber
CC BY-SA 3.0
2012-06-10T20:06:27.803Z
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.
domotorp
CC BY-SA 3.0
2012-06-09T17:14:46.760Z
2012-06-09T17:58:28.747Z
2012-06-09T17:58:28.747Z
Hermann Gruber
<p>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 &lt; instead of $\le$ to enhance non-tex readability.</p>

<p>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.</p>

<p>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.</p>

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

<p>Case L+A&lt;1/2: First Bob tells whether his input belongs to Y0 or not. If not, we have at most D&lt;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&lt;1/2 leaves left. If it does, then we have R&lt;1/2 leaves left.</p>

<p>Case L+B&lt;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&lt;1/2 leaves remaining. If not, we have at most D&lt;1/2 leaves remaining.</p>

<p>In all cases we are done. Let me know what you think.</p>

CC BY-SA 3.0
2011-11-01T22:14:37.657Z
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$.
Hermann Gruber
CC BY-SA 3.0
2011-10-31T21:10:24.437Z
2011-10-31T21:10:24.437Z
domotorp
<p>Besides <em>(deterministic) communication complexity</em> $cc(R)$ of a relation $R$, another basic measure for the amount of communication needed is the <em>protocol partition number</em> $pp(R)$. The relation between these two measures is known up to a constant factor. The monograph by Kushilevitz and Nisan (1997) gives </p>

<p>$$cc(R)/3 \le  \log_2(pp(R)) \le cc(R).$$ </p>

<p>Regarding the second inequality, it is easy to give (an infinite family of) relations $R$ with $\log_2(pp(R)) = cc(R)$. </p>

<p>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?  </p>

<p>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).  </p>

<p>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 <em>rectangle partition number</em>. </p>

<p><strong>EDIT:</strong> 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$? </p>

<p><strong>References</strong>:</p>

<ul>
<li>Kushilevitz, Eyal; Nisan, Noam: Communication Complexity. Cambridge University Press, 1997.</li>
<li>Kushilevitz, Eyal; Linial, Nathan; Ostrovsky, Rafail: The Linear-Array Conjecture in Communication Complexity is False, Combinatorica 19(2):241-254, 1999.</li>
<li>Doerr, Benjamin: Communication Complexity and the Protocol Partition Number, Technical Report 99-28, Berichtsreihe des Mathematischen Seminars der Universität Kiel, 1999.</li>
<li>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.</li>
</ul>

CC BY-SA 2.5
2011-01-14T05:35:00.520Z
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?
Marcos Villagra
CC BY-SA 2.5
2011-01-14T06:12:19.020Z
is this the author's home page? http://www.mpi-inf.mpg.de/~doerr/
Marcos Villagra
CC BY-SA 2.5
2011-01-14T07:33:58.867Z
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.
Hermann Gruber
CC BY-SA 2.5
2011-01-15T13:45:20.843Z
The only recent thing that might be useful that I know of is this paper http://www.lab2.kuis.kyoto-u.ac.jp/~kenya/MFCS2010.pdf.
Hartmut Klauck
CC BY-SA 3.0
2011-10-28T05:13:09.440Z
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...
domotorp
CC BY-SA 3.0
2011-10-30T20:19:44.987Z
Thanks for pointing out the mistake. The bounty is offered for a smaller constant than 2.223.
Hermann Gruber
<fl.formal-languages><lower-bounds><open-problem><regular-expressions><communication-complexity>
Protocol partition number and deterministic communication complexity
Hermann Gruber
# Protocol partition number and deterministic communication complexity

(Asked by: username_0 on 2011-01-13)

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.

**Tags:** fl.formal-languages, lower-bounds, open-problem, regular-expressions, communication-complexity
> **Comments:**
> **username_1**: 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?  
> **username_1**: is this the author's home page? http://www.mpi-inf.mpg.de/~doerr/  
> **username_0**: 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.  
> **username_2**: The only recent thing that might be useful that I know of is this paper http://www.lab2.kuis.kyoto-u.ac.jp/~kenya/MFCS2010.pdf.  
> **username_3**: 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...  
> **username_0**: Thanks for pointing out the mistake. The bounty is offered for a smaller constant than 2.223.  

---

## 2 answers

### Answer by username_3 on 2011-10-31. Score: 10 | Accepted answer

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.

> **Comments:**
> **username_0**: 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$.  

---

### Answer by username_0 on 2012-06-09. Score: 3

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.](http://www.thi.informatik.uni-frankfurt.de/~jukna/boolean/q.pdf) 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.

> **Comments:**
> **username_3**: This chapter is about Formulas and not Communication Complexity, but the proofs indeed look similar. Are these problems equivalent?  
> **username_0**: 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.)  
> **username_3**: 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.  

---

