Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR20-117 | 4th August 2020 16:08

New bounds on the half-duplex communication complexity



In this work, we continue the research started in [HIMS18], where the authors suggested to study the half-duplex communication complexity. Unlike the classical model of communication complexity introduced by Yao, in the half-duplex model, Alice and Bob can speak or listen simultaneously, as if they were talking using a walkie-talkie. The motivation for such a communication model comes from the study of the KRW conjecture. Following the open questions formulated in [HIMS18], we prove lower bounds for the disjointness function in all variants of half-duplex models and an upper bound in the half-duplex model with zero, that separates disjointness from the inner product function in this setting. Next, we prove lower and upper bounds on the half-duplex complexity of the Karchmer-Wigderson games for the counting functions and for the recursive majority function, adapting the ideas used in the classical communication complexity. Finally, we define the non-deterministic half-duplex complexity and establish bounds connecting it with non-deterministic complexity in the classical model.

ISSN 1433-8092 | Imprint