Half-duplex communication complexity with adversary can be less than the classical communication complexity
<|reference_start|>Half-duplex communication complexity with adversary can be less than the classical communication complexity: Half-duplex communication complexity with adversary was defined in [Hoover, K., Impagliazzo, R., Mihajlin, I., Smal, A. V. Half-Duplex Communication Complexity, ISAAC 2018.] Half-duplex communication protocols generalize classical protocols defined by Andrew Yao in [Yao, A. C.-C. Some Complexity Questions Related to Distributive Computing (Preliminary Report), STOC 1979]. It has been unknown so far whether the communication complexities defined by these models are different or not. In the present paper we answer this question: we exhibit a function whose half-duplex communication complexity with adversary is strictly less than its classical communication complexity.<|reference_end|>
@article{dektiarev2024half-duplex,
    title={Half-duplex communication complexity with adversary can be less than the
  classical communication complexity},
    author={Mikhail Dektiarev, Nikolay Vereshchagin},
    journal={arXiv preprint arXiv:2405.16881},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.16881},
    primaryClass={cs.CC cs.IT math.IT}
}