Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › Рецензирование
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.
Язык оригинала | английский |
---|---|
Название основной публикации | SOFSEM 2021 |
Подзаголовок основной публикации | Theory and Practice of Computer Science - 47th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2021, Proceedings |
Редакторы | Tomáš Bureš, Riccardo Dondi, Johann Gamper, Giovanna Guerrini, Tomasz Jurdzinski, Claus Pahl, Florian Sikora, Prudence W. Wong |
Издатель | Springer Nature |
Страницы | 233-248 |
Число страниц | 16 |
ISBN (печатное издание) | 9783030677305 |
DOI | |
Состояние | Опубликовано - 2021 |
Событие | 47th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2021 - Bolzano-Bozen, Италия Продолжительность: 25 янв 2021 → 29 янв 2021 |
Название | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Том | 12607 LNCS |
ISSN (печатное издание) | 0302-9743 |
ISSN (электронное издание) | 1611-3349 |
конференция | 47th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2021 |
---|---|
Страна/Tерритория | Италия |
Город | Bolzano-Bozen |
Период | 25/01/21 → 29/01/21 |
ID: 85250311