__
Revision #1 to TR23-011 | 24th May 2024 19:06
__
#### Half-duplex communication complexity with adversary? can be less than the classical communication complexity

**Abstract:**
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 the classical communication complexity.

**Changes to previous version:**
We added a new result: an example of a total function with linear gap between classical communication complexity and half-duplex complexity with weak adversary. We changed the terminology: weak adversary is called now honest adversary.

__
TR23-011 | 13th February 2023 13:39
__

#### Half-duplex communication complexity with adversary? can be less than the classical communication complexity

**Abstract:**
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 the classical communication complexity.