One-way communication complexity and non-adaptive decision trees

We study the relationship between various one-way communication complexity measures of a composed function with the analogous decision tree complexity of the outer function. We consider two gadgets: the AND function on 2 inputs, and the Inner Product on a constant number of inputs. More generally, we show the following when the gadget is Inner Product on 2b input bits for all b ≥ 2, denoted IP. If f is a total Boolean function that depends on all of its n input bits, then the bounded-error one-way quantum communication complexity of f ◦ IP equals Ω(n(b - 1)). If f is a partial Boolean function, then the deterministic one-way communication complexity of f ◦ IP is at least Ω(b · D→dt (f)), where D→dt (f) denotes non-adaptive decision tree complexity of f. To prove our quantum lower bound, we first show a lower bound on the VC-dimension of f ◦ IP. We then appeal to a result of Klauck [STOC’00], which immediately yields our quantum lower bound. Our deterministic lower bound relies on a combinatorial result independently proven by Ahlswede and Khachatrian [Adv. Appl. Math.’98], and Frankl and Tokushige [Comb.’99]. It is known due to a result of Montanaro and Osborne [arXiv’09] that the deterministic one-way communication complexity of f ◦ XOR equals the non-adaptive parity decision tree complexity of f. In contrast, we show the following when the inner gadget is the AND function on 2 input bits. There exists a function for which even the quantum non-adaptive AND decision tree complexity of f is exponentially large in the deterministic one-way communication complexity of f ◦ AND. However, for symmetric functions f, the non-adaptive AND decision tree complexity of f is at most quadratic in the (even two-way) communication complexity of f ◦ AND. In view of the first bullet, a lower bound on non-adaptive AND decision tree complexity of f does not lift to a lower bound on one-way communication complexity of f ◦ AND. The proof of the first bullet above uses the well-studied Odd-Max-Bit function. For the second bullet, we first observe a connection between the one-way communication complexity of f and the Möbius sparsity of f, and then give a lower bound on the Möbius sparsity of symmetric functions. An upper bound on the non-adaptive AND decision tree complexity of symmetric functions follows implicitly from prior work on combinatorial group testing; for the sake of completeness, we include a proof of this result. It is well known that the rank of the communication matrix of a function F is an upper bound on its deterministic one-way communication complexity. This bound is known to be tight for some F. However, in our final result we show that this is not the case when F = f ◦ AND. More precisely we show that for all f, the deterministic one-way communication complexity of F = f ◦ AND is at most (rank(MF))(1 - Ω(1)), where MF denotes the communication matrix of F.

• View at Publisher

Free Full Text ( Final Version , 847kb )