2021/05/05 by Mande, Nikhil S., Sanyal, Swagato, Sherif, Suhail · 1 citation
#Computational Complexity (cs.CC) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2105.01963
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. Let IP denote Inner Product on 2b bits. - If f is a total Boolean function that depends on all of its inputs, the bounded-error one-way quantum communication complexity of f ∘ IP equals Ω(n(b-1)). - If f is a partial Boolean function, the deterministic one-way communication complexity of f ∘ IP is at least Ω(b ⋅ Ddt→(f)), where Ddt→(f) denotes the non-adaptive decision tree complexity of f. Montanaro and Osborne [arXiv'09] observed that the deterministic one-way communication complexity of f ∘ XOR2 equals the non-adaptive parity decision tree complexity of f. In contrast, we show the following with the gadget AND2. - 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 ∘ AND2. - 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 ∘ AND2. In view of the first point, 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 ∘ AND2. In our final result we show that for all f, the deterministic one-way communication complexity of F = f ∘ AND2 is at most (rank(MF))(1 - Ω(1)), where MF denotes the communication matrix of F. This shows that the rank upper bound on one-way communication complexity (which can be tight in general) is not tight for AND-composed functions.