Reminder: This post contains 873 words
· 3 min read
· by Xianbin
Multi-party communication model is a generalization of the classical two-party communication model.
Definition
Given a set of \(k\) players, \(P_1,\ldots,P_k\) and \(k\) string each of which is \(n\)-bit. Any player \(P_i\) holds a string \(X_i\) but \(P_i\) can see strings but \(X_i\). It seems that that player \(P_i\) put \(X_i\) on the forehead (NOF).
The communication between parties is “writing on a blackboard” (broadcast): any bits sent by any party can be seen by all parties.
The \(\textbf{cost}\) in the multi-party communication model is the number of bits written on the blackboard.
A Toy Example
Consider the function \(\text{EQ}^k_n\). When \(k \geq 3\), two bits are enough for solving \(\text{EQ}^k_n\). Since a player can see \(\{X_2,\ldots,X_k\}\), it can return whether they are all equal or not by 1 or 0. Another player can check \(X_1, X_3\) and similarly return 1 or 0. By these two bits, we can solve the function \(\text{EQ}^k_n\).
Reference
[1]. Communication Complexity. Eyal Kushilevitz and Noam Nisan.