Deterministic communication complexity of refinement

Question

A partition of $[n]$ is a collection $\mathcal{P}$ of non-empty subsets of $[n]$ such that for each $i \in [n]$ there is a unique $P \in \mathcal{P}$ with $i \in P$. For partitions $\mathcal{P}, \mathcal{Q}$ we say that $\mathcal{P}$ refines $\mathcal{Q}$, denoted $\mathcal{P} \sqsubseteq \mathcal{Q}$, if for every $P \in \mathcal{P}$ there is some $Q \in \mathcal{Q}$ such that $P \subseteq Q$. Define the two party refinement problem by: $$ REF_n(\mathcal{P}, \mathcal{Q}) = \begin{cases} 1 & \text{ if } \mathcal{P} \sqsubseteq \mathcal{Q}, \\ 0 & \text{ otherwise. } \end{cases} $$ I studied the randomised communication complexity and showed that $\Omega(n) \le R^{cc}_{1/3}(REF_n) \le O(n \cdot log(n))$.

Is the deterministic communication complexity known for this problem?

Answer 1

The deterministic communication complexity of the problem is $\Theta(n\log{n})$: it is sufficient to show the existance of a family $S$ of partitions such that $|S|= 2^{\Omega(n\log{n})}$ and that for any $P_1,P_2 \in S$, $P_1$ refines $P_2$ iff $P_1 = P_2$, as this is a fooling set that implies a bound of $\Omega(n\log{n})$. Let $S$ be the set of partitions that partition $[n]$ into pairs (sets of size $= 2$). It is easy to see that $|S| \geq (n/2)! = 2^{\Omega(n\log{n})}$, and clearly no pair-partition is a refinement of another pair-partition. On the other hand, the problem can trivially be solved in $O(n\log{n})$ by having Alice send her entire input to Bob.