<p>Classical communication complexity requires one protocol (binary tree with edges labeled by bits Alice and Bob send) to solve the problem for every pair of inputs. What if we allow Alice and Bob to choose protocols separately depending on the input they have?</p>

<p>Consider the following communication model. Alice and Bob are trying to compute $f (x,y) $, $x $ is given to Alice, $y $ is given to Bob. At the begining of communication Alice chooses protocol $P_A =P_A (x) $, Bob chooses protocol  $P_B=P_B (y) $. They follow their protocols as in the classical case. They compute $f (x,y) $ if at the end they both come to leaves labeled with $f (x,y) $. </p>

<p>As $P_A $ is not necessary equal to $P_B $ at some round they may decide (according to their protocols) to either both send a bit or both wait for a bit - in these cases we say that the communication is invalid <strong>but Alice and Bob do not know about it</strong>: if they both send a bit they don't receive anything (as in half-duplex channels), if they both wait for a bit they receive "some" bit (uninitialized variable, potentially adversarial). </p>

<p>What is the relation to classical communication complexity? Trivially this model is at least as powerful as a classical one: Alice and Bob can use the same protocol for all inputs. Is it strictly more powerful? Is there any studies of this model? (I think I've seen something similar but I don't remember when and where.)</p>

CC BY-SA 3.0
2016-06-24T05:24:54.293Z
Interesting question. Can you give an example (even a contrived one) of where this would help? I have a hard time imagining that Bob could somehow actually make productive use of the bits he was receiving unless he knew what protocol Alice had chosen... On the flip side, I'm pretty sure that many lower bounds work just as well in this model. For example, the l.b. on Equality. Also rectangle covering-based l.b.'s should work just fine (they don't care if it's one protocol or many, just what bit gets sent at what stage).
Joshua Grochow
CC BY-SA 3.0
2016-06-24T05:25:57.657Z
Also, note that I'm pretty sure that any such "meta-protocol" can be pretty trivially modified to an equivalent one in which A always speaks first, and the players simply alternate sending bits. So I don't see that the whole thing about not knowing if they've sent a bit, half-duplex channels stuff actually has any serious effect... Or have I misunderstood what you're proposing?
Joshua Grochow
CC BY-SA 3.0
2016-06-24T05:53:05.757Z
It looks like you are right: you always can convert "meta"-protocol to normal one loosing the factor of 2. But it is still very interesting if there is an example where "meta"-protocol actually beat the normal one. If you ask me, I would conjecture that "meta"-protocol complexity is exactly equal to normal communication complexity.
ivmihajlin
CC BY-SA 3.0
2016-06-24T06:00:11.743Z
To see what potentially Alice and Bob can do with the "meta"-protocols, let's consider similar model, where if both are waiting for a bit, they receive 0. Then following protocol for Equality is correct: on i-th round send 1 if i-th bit of your input is 1, listen if i-th bit of your input is 0. If inputs are different after n rounds at least one player knows about it. So on n+1-th round send 1 if you know that inputs are different, listen otherwise. It is easy to see, that now both players know if the inputs are different. It doesn't beat the trivial protocol, but show that you can use "meta"
ivmihajlin
CC BY-SA 3.0
2016-06-25T10:50:27.727Z
See related work by Kerenidis et al. on zero-communication protocols.
András Salamon
CC BY-SA 3.0
2016-06-27T17:17:30.293Z
@JoshuaGrochow, thanks for your comments. Now it's clear that we can simulate any "meta"-protocol in this model of depth $D$ by the classical protocol of depth $2D$. In the applications we think of we care about multiplicative factors. So it is still interesting whether we can show an exact bound.
avsmal
CC BY-SA 3.0
2016-06-27T17:18:36.043Z
@AndrásSalamon, thanks, I will check it out.
avsmal
CC BY-SA 3.0
2016-06-27T20:01:38.387Z
@ivmihajlin: Nice example! However, it's not so much taking advantage of the "meta-protocol" aspect, as taking advantage of the ability to listen, and for "null bits" to be sent when no one speaks. Put another way: in your example, both players *know* what protocol the other is using, it's just that in some rounds neither person speaks. I believe that the ability to send "null bits" like this could be useful, but I still don't see how meta-protocols themselves could be useful.
Joshua Grochow
<communication-complexity>
Communication complexity protocols depending on inputs
avsmal
# Communication complexity protocols depending on inputs

(Asked by: username_0 on 2016-06-23)

Classical communication complexity requires one protocol (binary tree with edges labeled by bits Alice and Bob send) to solve the problem for every pair of inputs. What if we allow Alice and Bob to choose protocols separately depending on the input they have?

Consider the following communication model. Alice and Bob are trying to compute $f (x,y) $, $x $ is given to Alice, $y $ is given to Bob. At the begining of communication Alice chooses protocol $P\_A =P\_A (x) $, Bob chooses protocol $P\_B=P\_B (y) $. They follow their protocols as in the classical case. They compute $f (x,y) $ if at the end they both come to leaves labeled with $f (x,y) $.

As $P\_A $ is not necessary equal to $P\_B $ at some round they may decide (according to their protocols) to either both send a bit or both wait for a bit - in these cases we say that the communication is invalid **but Alice and Bob do not know about it**: if they both send a bit they don't receive anything (as in half-duplex channels), if they both wait for a bit they receive "some" bit (uninitialized variable, potentially adversarial).

What is the relation to classical communication complexity? Trivially this model is at least as powerful as a classical one: Alice and Bob can use the same protocol for all inputs. Is it strictly more powerful? Is there any studies of this model? (I think I've seen something similar but I don't remember when and where.)

**Tags:** communication-complexity

> **Comments:**
> **username_1**: Interesting question. Can you give an example (even a contrived one) of where this would help? I have a hard time imagining that Bob could somehow actually make productive use of the bits he was receiving unless he knew what protocol Alice had chosen... On the flip side, I'm pretty sure that many lower bounds work just as well in this model. For example, the l.b. on Equality. Also rectangle covering-based l.b.'s should work just fine (they don't care if it's one protocol or many, just what bit gets sent at what stage).  
> **username_1**: Also, note that I'm pretty sure that any such "meta-protocol" can be pretty trivially modified to an equivalent one in which A always speaks first, and the players simply alternate sending bits. So I don't see that the whole thing about not knowing if they've sent a bit, half-duplex channels stuff actually has any serious effect... Or have I misunderstood what you're proposing?  
> **username_2**: It looks like you are right: you always can convert "meta"-protocol to normal one loosing the factor of 2. But it is still very interesting if there is an example where "meta"-protocol actually beat the normal one. If you ask me, I would conjecture that "meta"-protocol complexity is exactly equal to normal communication complexity.  
> **username_2**: To see what potentially Alice and Bob can do with the "meta"-protocols, let's consider similar model, where if both are waiting for a bit, they receive 0. Then following protocol for Equality is correct: on i-th round send 1 if i-th bit of your input is 1, listen if i-th bit of your input is 0. If inputs are different after n rounds at least one player knows about it. So on n+1-th round send 1 if you know that inputs are different, listen otherwise. It is easy to see, that now both players know if the inputs are different. It doesn't beat the trivial protocol, but show that you can use "meta"  
> **username_3**: See related work by Kerenidis et al. on zero-communication protocols.  
> **username_0**: @JoshuaGrochow, thanks for your comments. Now it's clear that we can simulate any "meta"-protocol in this model of depth $D$ by the classical protocol of depth $2D$. In the applications we think of we care about multiplicative factors. So it is still interesting whether we can show an exact bound.  
> **username_0**: @AndrásSalamon, thanks, I will check it out.  
> **username_1**: @username_2: Nice example! However, it's not so much taking advantage of the "meta-protocol" aspect, as taking advantage of the ability to listen, and for "null bits" to be sent when no one speaks. Put another way: in your example, both players *know* what protocol the other is using, it's just that in some rounds neither person speaks. I believe that the ability to send "null bits" like this could be useful, but I still don't see how meta-protocols themselves could be useful.  

---

## 0 answers

