Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
In this work, we continue the research started in [6], 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-talki.e. The motivation for such a communication model comes from the study of the KRW conjecture. Following the open questions formulated in [6], we prove lower bounds for the disjointness function in all variants of half-duplex models and an upper bound in the half-duplex model with zero, that separates disjointness from the inner product function in this setting. Next, we prove lower and upper bounds on the half-duplex complexity of the Karchmer-Wigderson games for the counting functions and for the recursive majority function, adapting the ideas used in the classical communication complexity. Finally, we define the non-deterministic half-duplex complexity and establish bounds connecting it with non-deterministic complexity in the classical model.
Original language | English |
---|---|
Title of host publication | SOFSEM 2021 |
Subtitle of host publication | Theory and Practice of Computer Science - 47th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2021, Proceedings |
Editors | Tomáš Bureš, Riccardo Dondi, Johann Gamper, Giovanna Guerrini, Tomasz Jurdzinski, Claus Pahl, Florian Sikora, Prudence W. Wong |
Publisher | Springer Nature |
Pages | 233-248 |
Number of pages | 16 |
ISBN (Print) | 9783030677305 |
DOIs | |
State | Published - 2021 |
Event | 47th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2021 - Bolzano-Bozen, Italy Duration: 25 Jan 2021 → 29 Jan 2021 |
Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Volume | 12607 LNCS |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference | 47th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2021 |
---|---|
Country/Territory | Italy |
City | Bolzano-Bozen |
Period | 25/01/21 → 29/01/21 |
ID: 85250311