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.

  • $\begingroup$ 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? $\endgroup$ Sep 11, 2018 at 12:12
  • 1
    $\begingroup$ 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. $\endgroup$
    – domotorp
    Sep 11, 2018 at 18:38
  • $\begingroup$ 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)?" $\endgroup$ Sep 12, 2018 at 7:10
  • $\begingroup$ Yes.$\;\;\!\!\!$ $\endgroup$
    – domotorp
    Sep 12, 2018 at 7:45


Your Answer

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

Browse other questions tagged or ask your own question.