We continue the study of half-duplex communication complexity, a model introduced in [HIMS18] and further studied in [DISSU21], in which each player can either send a bit or listen in each round, similarly to communication over a walkie-talkie.
We prove improved upper bounds for the Inner Product function in the ... more >>>

In this paper, we prove a super-cubic lower bound on the size of a communication protocol for generalized Karchmer-Wigderson game for some explicit function $f: \{0,1\}^n\to \{0,1\}^{\log n}$. Lower bounds for original Karchmer-Wigderson games correspond to De Morgan formula lower bounds, thus the best known size lower bound is cubic. ... more >>>

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. ... more >>>