ECCC-Report TR23-011https://eccc.weizmann.ac.il/report/2023/011Comments and Revisions published for TR23-011en-usWed, 15 Feb 2023 18:19:34 +0200
Paper TR23-011
| Half-duplex communication complexity with adversary? can be less than the classical communication complexity |
Nikolay Vereshchagin,
Mikhail Dektiarev
https://eccc.weizmann.ac.il/report/2023/011Half-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 the classical communication complexity.Wed, 15 Feb 2023 18:19:34 +0200https://eccc.weizmann.ac.il/report/2023/011