We give new characterizations and lower bounds relating classes in the communication complexity polynomial hierarchy and circuit complexity to limited memory communication models.

We introduce the notion of rectangle overlay complexity of a function f:01n01n01 . This is a natural combinatorial complexity measure in terms of combinatorial rectangles in the communication matrix of f. Furthermore, we consider memoryless and limited-memory communication models, originally introduced in [11] with slightly different terminology. In these communication models there are two parameters of interest: (i) the message length or space, and (ii) the number of memory states. Specifically, these are one-way protocols which proceed in rounds. In each round, Alice sends one message of bounded length to Bob; receiving a message from Alice, Bob has to decide on the spot whether to output 0 or 1, or to continue the protocol. If he decides to continue, he immediately forgets Alice's message. In memoryless protocols, no memory is transferred between different rounds (but Bob still has ``space'' to hold Alice's messages within each round). We can make Bob more powerful by giving him some constant size memory, which he can update at the end of each round.

We show that rectangle overlays completely characterize memoryless protocols. Then, we go on to show several connections to the communication complexity polynomial hierarchy defined by Babai, Frankl and Simon in 1986 [6]. This hierarchy has recently regained attention because its connection to the algebrization barrier in complexity theory [1]. We show that PNP is completely characterized by memoryless protocols with polylog(n) space (message length), and thus it admits a purely combinatorial characterization in terms of rectangle overlays. If in addition Bob is given 3 states of memory besides polylog(n) space (message length), Alice and Bob can compute every level of kcc in the communication complexity hierarchy (for constant k), and also every function in AC0. Furthermore, we show that a 5-state Bob with polylog(n) space (message length) can compute exactly the functions in the communication class PSPACEcc. This gives the first meaningful characterization of PSPACEcc in terms of space, originally defined in [6] without any notion of space. We also study equivalences and separations between our limited memory communication model and branching programs, and relations to circuit classes.