New answers tagged


Not exactly what you are asking but the DAG-like version of this model has been studied, here are some recent references in case it helps: Hrubeš, Pavel; Pudlák, Pavel, A note on monotone real circuits, Inf. Process. Lett. 131, 15-19 (2018). ZBL1422.68115. Sokolov, Dmitry, Dag-like communication and its applications, ZBL06763514.


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

Top 50 recent answers are included