Space-Bounded Communication Complexity

In the past thirty years, Communication Complexity has emerged as a foundational tool to proving lower bounds in many areas of computer science. Its power comes from its generality, but this generality comes at a price—no superlinear communication lower bound is possible, since a player may communicate his entire input. However, what if the players are limited in their ability to recall parts of their interaction? We introduce memory models for 2-party communication complexity. Our general model is as follows: two computationally unrestricted players, Alice and Bob, each have s(n) bits of memory. When a player receives a bit of communication, he “compresses ” his state. This compression may be an arbitrary function of his current memory contents, his input, and the bit of communication just received; the only restriction is that the compression must return at most s(n) bits. We obtain memory hierarchy theorems (also comparing this general model with its restricted variants), and show super-linear lower bounds for some explicit (non-boolean) functions. Our main conceptual and technical contribution concerns the following variant. The com