Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #3 to TR20-117 | 7th July 2021 17:36

New bounds on the half-duplex communication complexity

RSS-Feed




Revision #3
Authors: Yuriy Dementiev, Artur Ignatiev, Vyacheslav Sidelnik, Alexander Smal, Mikhail Ushakov
Accepted on: 7th July 2021 17:36
Downloads: 284
Keywords: 


Abstract:

In this work, we continue the research started in [HIMS18], 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-talkie. The motivation for such a communication model comes from the study of the KRW conjecture. Following the open questions formulated in [HIMS18], 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. 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.



Changes to previous version:

Changes corresponding to a flaw found in HIMS18: now we do not claim that our bounds separate inner product and disjointness.


Revision #2 to TR20-117 | 16th March 2021 13:22

New bounds on the half-duplex communication complexity





Revision #2
Authors: Yuriy Dementiev, Artur Ignatiev, Vyacheslav Sidelnik, Alexander Smal, Mikhail Ushakov
Accepted on: 16th March 2021 13:22
Downloads: 274
Keywords: 


Abstract:

In this work, we continue the research started in [HIMS18], where the authors proposed 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-talkie. The motivation for such a communication model comes from the study of the KRW conjecture. Following the open questions formulated in [HIMS18], 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 communication complexity and establish bounds connecting it with non-deterministic communication complexity in the classical model.



Changes to previous version:

A flaw in Theorem 4 was fixed. The resulting lower bounds were corrected. See Remark 1 for more details.


Revision #1 to TR20-117 | 25th November 2020 13:10

New bounds on the half-duplex communication complexity





Revision #1
Authors: Yuriy Dementiev, Artur Ignatiev, Vyacheslav Sidelnik, Alexander Smal, Mikhail Ushakov
Accepted on: 25th November 2020 13:10
Downloads: 602
Keywords: 


Abstract:

In this work, we continue the research started in [HIMS18], 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-talkie. The motivation for such a communication model comes from the study of the KRW conjecture. Following the open questions formulated in [HIMS18], 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.



Changes to previous version:

Multiple typos fixed.


Paper:

TR20-117 | 4th August 2020 16:08

New bounds on the half-duplex communication complexity


Abstract:

In this work, we continue the research started in [HIMS18], 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-talkie. The motivation for such a communication model comes from the study of the KRW conjecture. Following the open questions formulated in [HIMS18], 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.



ISSN 1433-8092 | Imprint