2
$\begingroup$

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)$$

$\endgroup$
0

1 Answer 1

2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Oh yes, this is obvious. How did I miss this? Anyway, thanks for this answer. $\endgroup$
    – gen
    Aug 19, 2021 at 1:15

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.