4
$\begingroup$

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.

$\endgroup$
  • $\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$ – Marzio De Biasi Sep 11 '18 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 '18 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$ – Marzio De Biasi Sep 12 '18 at 7:10
  • $\begingroup$ Yes.$\;\;\!\!\!$ $\endgroup$ – domotorp Sep 12 '18 at 7:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.