T1: Multi-party Communication Model (NOF)

August 14, 2024

• Definition
• A Toy Example
• Reference

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.