  We define the Streaming Communication model that combines the main aspects of
communication complexity and streaming. We consider two agents that want to
compute some function that depends on inputs that are distributed to each
agent. The inputs arrive as data streams and each agent has a bounded memory.
Agents are allowed to communicate with each other and also update their memory
based on the input bit they read and the previous message they received.
  We provide tight tradeoffs between the necessary resources, i.e.
communication and memory, for some of the canonical problems from communication
complexity by proving a strong general lower bound technique. Second, we
analyze the Approximate Matching problem and show that the complexity of this
problem (i.e. the achievable approximation ratio) in the one-way variant of our
model is strictly different both from the streaming complexity and the one-way
communication complexity thereof.

Computational Complexity