# T1: Multi-party Communication Model (NOF)

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.