Half-duplex communication complexity with adversary can be less than the classical communication complexity
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909211227586560 |
|---|---|
| author | Dektiarev, Mikhail Vereshchagin, Nikolay |
| author_facet | Dektiarev, Mikhail Vereshchagin, Nikolay |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_16881 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Half-duplex communication complexity with adversary can be less than the classical communication complexity Dektiarev, Mikhail Vereshchagin, Nikolay Computational Complexity Information Theory 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. |
| title | Half-duplex communication complexity with adversary can be less than the classical communication complexity |
| topic | Computational Complexity Information Theory |
| url | https://arxiv.org/abs/2405.16881 |