Let f be a Boolean function on n variables. Let $DC(g)$ and $D(g)$ denote the deterministic communication complexity and the decision tree complexity of $g$. Why is the following inequality true:
$$DC(f(x \land y)) \leq 2 D(f)$$
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this communityGiven a decision tree for $f(z)$, we can simulate it in the communication model in the following way: whenever the decision tree queries $z_i$, Alice sends $x_i$ and Bob sends $y_i$, and now both of them know $x_i \land y_i$ and can proceed. We are using two bits of communication per query, hence the bound.