# Deterministic communication complexity of refinement

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?

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.