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

CC BY-SA 4.0
2021-12-27T05:16:06.027Z
I don't have a reference, I just noticed it can be solved using standard techniques
user3209423940248
CC BY-SA 4.0
2021-12-26T15:40:43.830Z
2021-12-26T15:40:43.830Z
user3209423940248
<p>A partition of <span class="math-container">$[n]$</span> is a collection <span class="math-container">$\mathcal{P}$</span> of non-empty subsets of <span class="math-container">$[n]$</span> such that for each <span class="math-container">$i \in [n]$</span> there is a unique <span class="math-container">$P \in \mathcal{P}$</span> with <span class="math-container">$i \in P$</span>. For partitions <span class="math-container">$\mathcal{P}, \mathcal{Q}$</span> we say that <span class="math-container">$\mathcal{P}$</span> <em>refines</em> <span class="math-container">$\mathcal{Q}$</span>, denoted <span class="math-container">$\mathcal{P} \sqsubseteq \mathcal{Q}$</span>, if for every <span class="math-container">$P \in \mathcal{P}$</span> there is some <span class="math-container">$Q \in \mathcal{Q}$</span> such that <span class="math-container">$P \subseteq Q$</span>. Define the two party <em>refinement problem</em> by:
<span class="math-container">$$
REF_n(\mathcal{P}, \mathcal{Q}) = 
\begin{cases}
1 &amp; \text{ if } \mathcal{P} \sqsubseteq \mathcal{Q}, \\
0 &amp; \text{ otherwise. }
\end{cases}
$$</span>
I studied the randomised communication complexity and showed that <span class="math-container">$\Omega(n) \le R^{cc}_{1/3}(REF_n) \le O(n \cdot log(n))$</span>.</p>
<p>Is the deterministic communication complexity known for this problem?</p>

<randomized-algorithms><communication-complexity>
Deterministic communication complexity of refinement
user1868607
# Deterministic communication complexity of refinement

(Asked by: username_0 on 2021-12-26)

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?

**Tags:** randomized-algorithms, communication-complexity

---

## 1 answers

### Answer by username_1 on 2021-12-26. Score: 4 | Accepted answer

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.

> **Comments:**
> **username_1**: I don't have a reference, I just noticed it can be solved using standard techniques  

---

