Abstract
We study the relationship between various oneway 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 boundederror oneway quantum communication complexity of f∘IP equals Ω(n(b1)).
 If f is a partial Boolean function, then the deterministic oneway communication complexity of f∘IP is at least Ω(b ⋅ 𝖣_{dt}^ → (f)), where 𝖣_{dt}^ → (f) denotes nonadaptive decision tree complexity of f. To prove our quantum lower bound, we first show a lower bound on the VCdimension 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 oneway communication complexity of f∘XOR equals the nonadaptive 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 nonadaptive AND decision tree complexity of f is exponentially large in the deterministic oneway communication complexity of f∘AND.
 However, for symmetric functions f, the nonadaptive AND decision tree complexity of f is at most quadratic in the (even twoway) communication complexity of f∘AND. In view of the first bullet, a lower bound on nonadaptive AND decision tree complexity of f does not lift to a lower bound on oneway communication complexity of f∘AND. The proof of the first bullet above uses the wellstudied OddMaxBit function. For the second bullet, we first observe a connection between the oneway 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 nonadaptive 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 oneway 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 oneway communication complexity of F = f∘AND is at most (rank(M_{F}))(1  Ω(1)), where M_{F} denotes the communication matrix of F.
BibTeX  Entry
@InProceedings{mande_et_al:LIPIcs.STACS.2022.49,
author = {Mande, Nikhil S. and Sanyal, Swagato and Sherif, Suhail},
title = {{OneWay Communication Complexity and NonAdaptive Decision Trees}},
booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
pages = {49:149:24},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772228},
ISSN = {18688969},
year = {2022},
volume = {219},
editor = {Berenbrink, Petra and Monmege, Benjamin},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15859},
URN = {urn:nbn:de:0030drops158598},
doi = {10.4230/LIPIcs.STACS.2022.49},
annote = {Keywords: Decision trees, communication complexity, composed Boolean functions}
}
Keywords: 

Decision trees, communication complexity, composed Boolean functions 
Collection: 

39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022) 
Issue Date: 

2022 
Date of publication: 

09.03.2022 