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 #6 to TR18-089 | 7th July 2021 17:30

Half-duplex communication complexity

RSS-Feed




Revision #6
Authors: Kenneth Hoover, Russell Impagliazzo, Ivan Mihajlin, Alexander Smal
Accepted on: 7th July 2021 17:30
Downloads: 24
Keywords: 


Abstract:

Suppose Alice and Bob are communicating in order to compute some function $f$, but instead of a conventional communication channel, they have a pair of walkie-talkie devices. They can use some classical communication protocol for $f$, where every round one of the players sends a bit, and the other receives it. The question is whether talking via walkie-talkie gives them more power? Using walkie-talkies instead of a classical communication channel allows players two extra possibilities: to speak simultaneously (but in this case they do not hear each other) and to listen at the same time (but in this case they do not transfer any bits). The motivation for this kind of communication model comes from the study of the KRW conjecture. We show that for some definitions, this non-classical communication model is, in fact, more powerful than the classical one as it allows to compute some functions in a smaller number of rounds. We also prove lower bounds for these models using both combinatorial and information-theoretic methods.



Changes to previous version:

In the previous versions on this paper including the conference version we claimed better lower bounds for $IP_n$ in all tree half-duplex models based on an information theoretic approach.
Unfortunately, proofs of these results (Theorems 18, 21, and 24) contain a critical flaw (Lemma~13 in is not true).
Moreover, as far as we know, this flaw can not be fixed --- there is an upper bound of $n/2+2$ on half-duplex complexity of $IP_n$ with silence (proven by Tatiana Gladysh) that matches the lower bound proven here up to an additive constant $2$.
This upper bound contradicts the lower bound claimed in the previous versions of the paper.
All these theorems were removed from the paper preserving numeration of other theorems.


Revision #5 to TR18-089 | 1st August 2020 00:35

Half-duplex communication complexity





Revision #5
Authors: Kenneth Hoover, Russell Impagliazzo, Ivan Mihajlin, Alexander Smal
Accepted on: 1st August 2020 00:35
Downloads: 129
Keywords: 


Abstract:

Suppose Alice and Bob are communicating in order to compute some function $f$, but instead of a conventional communication channel, they have a pair of walkie-talkie devices. They can use some classical communication protocol for $f$, where every round one of the players sends a bit, and the other receives it. The question is whether talking via walkie-talkie gives them more power? Using walkie-talkies instead of a classical communication channel allows players two extra possibilities: to speak simultaneously (but in this case they do not hear each other) and to listen at the same time (but in this case they do not transfer any bits). The motivation for this kind of communication model comes from the study of the KRW conjecture. We show that for some definitions, this non-classical communication model is, in fact, more powerful than the classical one as it allows to compute some functions in a smaller number of rounds. We also prove lower bounds for these models using both combinatorial and information-theoretic methods.



Changes to previous version:

The theorem numbering changed - now it is synchronized with the ISAAC publication.


Revision #4 to TR18-089 | 24th July 2020 01:36

Half-duplex communication complexity





Revision #4
Authors: Kenneth Hoover, Russell Impagliazzo, Ivan Mihajlin, Alexander Smal
Accepted on: 24th July 2020 01:36
Downloads: 98
Keywords: 


Abstract:

Suppose Alice and Bob are communicating in order to compute some function $f$, but instead of a conventional communication channel, they have a pair of walkie-talkie devices. They can use some classical communication protocol for $f$, where every round one of the players sends a bit, and the other receives it. The question is whether talking via walkie-talkie gives them more power? Using walkie-talkies instead of a classical communication channel allows players two extra possibilities: to speak simultaneously (but in this case they do not hear each other) and to listen at the same time (but in this case they do not transfer any bits). The motivation for this kind of communication model comes from the study of the KRW conjecture. We show that for some definitions, this non-classical communication model is, in fact, more powerful than the classical one as it allows to compute some functions in a smaller number of rounds. We also prove lower bounds for these models using both combinatorial and information-theoretic methods.



Changes to previous version:

+ Acknowledgement


Revision #3 to TR18-089 | 22nd July 2020 02:32

Half-duplex communication complexity





Revision #3
Authors: Kenneth Hoover, Russell Impagliazzo, Ivan Mihajlin, Alexander Smal
Accepted on: 22nd July 2020 02:32
Downloads: 104
Keywords: 


Abstract:

Suppose Alice and Bob are communicating bits to each other in order to compute some function $f$, but instead of a classical communication channel they have a pair of walkie-talkie devices. They can use some classical communication protocol for $f$ where each round one player sends bit and the other one receives it. The question is whether talking via walkie-talkie gives them more power? Using walkie-talkie instead of a classical communication channel allows players two extra possibilities: to speak simultaneously (but in this case they do not hear each other) and to listen at the same time (but in this case they do not transfer any bits). We show that for some definitions this non-classical communication model is, in fact, more powerful than the classical one as it allows to compute some functions in a smaller number of rounds. We also introduce round elimination technique for proving lower bounds in this setting and use it to prove lower bounds for some Boolean functions.



Changes to previous version:

The proof of Theorem 9 was simplified.


Revision #2 to TR18-089 | 21st July 2018 21:02

Half-duplex communication complexity





Revision #2
Authors: Kenneth Hoover, Russell Impagliazzo, Ivan Mihajlin, Alexander Smal
Accepted on: 21st July 2018 21:02
Downloads: 494
Keywords: 


Abstract:

Suppose Alice and Bob are communicating in order to compute some function $f$, but instead of a classical communication channel they have a pair of walkie-talkie devices. They can use some classical communication protocol for $f$ where each round one player sends a bit and the other one receives it. The question is whether talking via walkie-talkie gives them more power? Using walkie-talkies instead of a classical communication channel allows players two extra possibilities: to speak simultaneously (but in this case they do not hear each other) and to listen at the same time (but in this case they do not transfer any bits). The motivation for this kind of a communication model comes from the study of the KRW conjecture. We show that for some definitions this non-classical communication model is, in fact, more powerful than the classical one as it allows to compute some functions in a smaller number of rounds. We also prove lower bounds for these models using both combinatorial and information theoretic methods.



Changes to previous version:

New lower bounds via theoretical information methods.


Revision #1 to TR18-089 | 16th May 2018 12:28

Half-duplex communication complexity





Revision #1
Authors: Kenneth Hoover, Russell Impagliazzo, Ivan Mihajlin, Alexander Smal
Accepted on: 16th May 2018 12:28
Downloads: 369
Keywords: 


Abstract:

Suppose Alice and Bob are communicating bits to each other in order to compute some function $f$, but instead of a classical communication channel they have a pair of walkie-talkie devices. They can use some classical communication protocol for $f$ where each round one player sends bit and the other one receives it. The question is whether talking via walkie-talkie gives them more power? Using walkie-talkie instead of a classical communication channel allows players two extra possibilities: to speak simultaneously (but in this case they do not hear each other) and to listen at the same time (but in this case they do not transfer any bits). We show that for some definitions this non-classical communication model is, in fact, more powerful than the classical one as it allows to compute some functions in a smaller number of rounds.
We introduce round elimination technique for proving lower bounds in this setting and use it to prove lower bounds for some Boolean functions. We also apply information theoretic methods to prove
better lower bounds for one of the models.



Changes to previous version:

We apply information theoretic methods to prove lower bounds on the half-duplex complexity with adversary.


Paper:

TR18-089 | 27th April 2018 02:02

Half-duplex communication complexity


Abstract:

Suppose Alice and Bob are communicating bits to each other in order to compute some function $f$, but instead of a classical communication channel they have a pair of walkie-talkie devices. They can use some classical communication protocol for $f$ where each round one player sends bit and the other one receives it. The question is whether talking via walkie-talkie gives them more power? Using walkie-talkie instead of a classical communication channel allows players two extra possibilities: to speak simultaneously (but in this case they do not hear each other) and to listen at the same time (but in this case they do not transfer any bits). We show that for some definitions this non-classical communication model is, in fact, more powerful than the classical one as it allows to compute some functions in a smaller number of rounds. We also introduce round elimination technique for proving lower bounds in this setting and use it to prove lower bounds for some Boolean functions.



ISSN 1433-8092 | Imprint