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?


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

  • $\begingroup$ I don't have a reference, I just noticed it can be solved using standard techniques $\endgroup$ Commented Dec 27, 2021 at 5:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.