2026-07-24T14:22:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15859 2024-03-06T10:56:22Z ddc:004 open_access

One-Way Communication Complexity and Non-Adaptive Decision Trees Mande, Nikhil S. Sanyal, Swagato Sherif, Suhail Decision trees communication complexity composed Boolean functions 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 ⋅ 𝖣_{dt}^ → (f)), where 𝖣_{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(M_{F}))(1 - Ω(1)), where M_{F} denotes the communication matrix of F. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nikhil S. Mande and Swagato Sanyal and Suhail Sherif 2022 Is Part Of LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2022.49 urn:nbn:de:0030-drops-158598 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.49 eng https://creativecommons.org/licenses/by/4.0/legalcode