ECCC-Report TR18-089https://eccc.weizmann.ac.il/report/2018/089Comments and Revisions published for TR18-089en-usSat, 21 Jul 2018 21:02:09 +0300
Revision 2
| Half-duplex communication complexity |
Kenneth Hoover,
Russell Impagliazzo,
Ivan Mihajlin,
Alexander Smal
https://eccc.weizmann.ac.il/report/2018/089#revision2Suppose 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.Sat, 21 Jul 2018 21:02:09 +0300https://eccc.weizmann.ac.il/report/2018/089#revision2
Revision 1
| Half-duplex communication complexity |
Kenneth Hoover,
Russell Impagliazzo,
Ivan Mihajlin,
Alexander Smal
https://eccc.weizmann.ac.il/report/2018/089#revision1Suppose 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.Wed, 16 May 2018 12:28:13 +0300https://eccc.weizmann.ac.il/report/2018/089#revision1
Paper TR18-089
| Half-duplex communication complexity |
Kenneth Hoover,
Russell Impagliazzo,
Ivan Mihajlin,
Alexander Smal
https://eccc.weizmann.ac.il/report/2018/089Suppose 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.Tue, 01 May 2018 22:03:23 +0300https://eccc.weizmann.ac.il/report/2018/089