Brief introduction:

In two-party communication complexity, as presented by Yao in 1979, we model protocols as binary trees whose internal nodes are labeled by either Alice or Bob, and the leaves are labeled with possible A node labeled by Alice is a step in the protocol in which she speaks. In these nodes that belongs to Alice, she computes a function which relies solely on her input $x$, and outputs a single bit which states whether to go left or right in the tree. Likewise for Bob, with his input $y$. The computation itself is a traversal over the protocol tree; since both Alice and Bob hear all the messages that are sent in the protocol, they both know the common state in which they stand, they can traverse the protocol tree together and reach the same leaf.

When discussing multiparty communication complexity, an immediate question that arises is the model of communication. In case of broadcast communication, commonly known as "the blackboard model", we can still formulate protocols as trees, and since everyone hears all of the communication, they can all traverse the protocol tree together. However, in case of point-to-point communication, commonly known as "the message passing model", such a model does not seem to work. In most papers, this model is presented as "in the message passing model, there are $\ell$ players that can send each other messages over private channels between each two players", and that's it.

The question:

Do you know of any simple combinatorial way of modeling such protocols? Or can you think of such a way?

Thanks in advance.


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.