3
$\begingroup$

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.)

$\endgroup$
  • 2
    $\begingroup$ 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). $\endgroup$ – Joshua Grochow Jun 24 '16 at 5:24
  • 1
    $\begingroup$ 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? $\endgroup$ – Joshua Grochow Jun 24 '16 at 5:25
  • 1
    $\begingroup$ 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. $\endgroup$ – ivmihajlin Jun 24 '16 at 5:53
  • 1
    $\begingroup$ 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" $\endgroup$ – ivmihajlin Jun 24 '16 at 6:00
  • 1
    $\begingroup$ See related work by Kerenidis et al. on zero-communication protocols. $\endgroup$ – András Salamon Jun 25 '16 at 10:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.