Multiparty communication complexity

In the 2–party communication game, introduced in in 1979, two players, P₁ and P₂ attempt to compute a Boolean function

$f(x_{1},x_{2}):\{0,1\}^{n}\to \{0,1\},\ x_{1},x_{2}\in \{0,1\}^{n'},\ \$2n'=n$

Player P₁ knows the value of x₂, P₂ knows the value of x₁, but P_i does not know the value of x_i, for i=1,2.

In other words, the players know the other's variables, but not their own. The minimum number of bits that must be communicated by the players to compute f is the communication complexity of f, denoted by κ(f).

The multiparty communication game, defined in 1983 , it is a powerful generalization of the 2–party case: Here the players know all the others' input, except their own. Because of this property, sometimes this model is called "numbers on the foreheadˇ model, since if the players were seated around a roundtable, each wearing their own input on the forehead, then every player would see all the others' input, except their own.

The formal definition is as follows: k players: P₁,P₂,...,P_k intend to compute a Boolean function

$f(x_{1},x_{2},...,x_{n}):\{0,1\}^{n}\to \{0,1\}$

On set S={x₁,x₂,...,x_n} of variables there is a fixed partition $A$ of $k$ classes $A_1,A_2,...,A_k$, and player $P_i$ knows every variable, {\em except} those in $A_i$, for $i=1,2,...,k$. The players have unlimited computational power, and they

communicate with the 
help of a blackboard, viewed by all players.