Protocol partition number and deterministic communication complexity
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.

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

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.

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.

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