To explain the connection to data streams, almost all known lower bound arguments on the memory required of a data stream algorithm are proven via communication complexity, or at least can be reformulated using communication complexity.
The basic idea is to partition the elements of an input stream contiguously, consisting of say \(k\)  elements, into a possibly smaller number \(t\)  of players.
Then one argues that if there is a data stream algorithm solving the problem, then the communication problem can be solved by passing the memory contents as messages from player to player.
Note that this naturally gives rise to the one-way number-in-hand model.
Since the total communication cost is \(t \cdot S\) , where \(S\)  is the size of the memory of the streaming algorithm, if the randomized \(t\) -player communication complexity of the function \(f\)  is \(CC_t\) , we must have \(S \ge CC_t/t\) .
Many lower bounds in data streams are proven already with two players.
However, it is known that for some functions more players are needed to obtain stronger lower bounds, such as for estimating the frequency moments in insertion only streams (see, e.g.,
[1]}, [2]} and references therein).
