TY - GEN

T1 - New Bounds on the Half-Duplex Communication Complexity

AU - Smal, Alexander

AU - Сидельник, Вячеслав Андреевич

AU - Дементьев, Юрий Ильич

AU - Игнатьев, Артур Андреевич

AU - Ушаков, Михаил Сергеевич

N1 - Publisher Copyright: © 2021, Springer Nature Switzerland AG.

PY - 2021

Y1 - 2021

N2 - 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.

AB - 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.

KW - Communication complexity

KW - Half-duplex communication

KW - Karchmer-wigderson games

UR - http://www.scopus.com/inward/record.url?scp=85101546798&partnerID=8YFLogxK

UR - https://www.mendeley.com/catalogue/c6bcb8da-7c64-387b-8445-62bf41477f28/

U2 - 10.1007/978-3-030-67731-2_17

DO - 10.1007/978-3-030-67731-2_17

M3 - Conference contribution

AN - SCOPUS:85101546798

SN - 9783030677305

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 233

EP - 248

BT - SOFSEM 2021

A2 - Bureš, Tomáš

A2 - Dondi, Riccardo

A2 - Gamper, Johann

A2 - Guerrini, Giovanna

A2 - Jurdzinski, Tomasz

A2 - Pahl, Claus

A2 - Sikora, Florian

A2 - Wong, Prudence W.

PB - Springer Nature

T2 - 47th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2021

Y2 - 25 January 2021 through 29 January 2021

ER -