DOI

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 янв 202129 янв 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/2129/01/21

    Предметные области Scopus

  • Теоретические компьютерные науки
  • Компьютерные науки (все)

ID: 85250311