# Tag Info

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