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 smaller number of rounds.

We also introduce round elimination technique for proving lower bounds in this setting and use it to prove

... more