# What is the exact communication complexity of subtree disjointness?

A classic textbook example for communication complexity is when A and B both receive a subtree of a an $$n$$-node tree (that they both know), and they need to output whether their subtrees are disjoint or not. The textbook solution usually gives an algorithm with $$2\log_2 n$$ bits of communication. In Lovasz-Saks, however, there is a better algorithm, with $$\log_2 n+\log_2 \log_2 n$$ bits of communication. Where is the truth between this and the trivial $$\log_2 n$$ lower bound?

A natural idea is to consider the rank of the communication matrix, but this is $$2n-1$$ for any tree; the vertices and edges generate every subtree.

• Do you mean non-deterministic comm. complexity of subtree disjointness? In R.L. Graham, Handbook of Combinatorics, 1995; after describing the protocol ("A sends any node x of her tree to B; if y is the node in B's tree that is closest to x, B responds by sending y to A; then A checks if y in TA") they say: "... this (non-deterministic) protocol uses $2 \log n$ bits. Lovasz and Saks (1993) showed that it can be modified to use only $\log n + \log \log n$ bits...". What is the trivial protocol for $\log_2 n$ LB? – Marzio De Biasi Sep 11 '18 at 12:12
• No, I mean deterministic; non-deterministic bounds are trivially $\log n$, as either you can output a common vertex, or a separating vertex. The LB follows by noticing that the communication matrix is triangular if the tree is a path which assuredly A holds the left, and B the right end-vertex of. – domotorp Sep 11 '18 at 18:38
• Thanks for the clarification (I misinterpreted it)! So, when you say "Where is the truth ...?" you mean "Has the known bounds $\log n \leq \kappa( C_T) \leq \log n + \log \log n$ been improved (or solved)?" – Marzio De Biasi Sep 12 '18 at 7:10
• Yes.$\;\;\!\!\!$ – domotorp Sep 12 '18 at 7:45