Overlays and Limited Memory Communication

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 {0, 1}n × {0, 1}ⁿ→{0, 1}. This is a natural combinatorial complexity measure in terms of combinatorial rectangles in the communication matrix of f. Furthermore, we consider memory less and limited-memory communication models, originally introduced in Brody, Chen, Papakonstantinou, Song, and Sun with slightly different terminology. In these communication models there are two parameters of interest: The maximum message length s (which we think of as space) and the number of memory states w. Specifically, these are one-way protocols which proceed in rounds. In each round, Alice sends a message of at most s bits 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 memory less 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 w memory states. He can change into a new state at the end of each round. We show that rectangle overlays completely characterize memory less protocols. Then, we go on to show several connections to the communication complexity polynomial hierarchy defined by Babai, Frankl and Simon in 1986. This hierarchy has recently regained attention because its connection to the algebrization barrier in complexity theory (Aaronson and Wigderson, 2009). We show that P^NPcc is completely characterized by memory less protocols with polylog(n) space (maximum message length), and thus it admits a purely combinatorial characterization in terms of rectangle overlays. If Bob has 3 memory states and Alice sends messages- of length polylog(n), they can compute every level of Sigma_k in the communication complexity hierarchy (for constant k), and also every function in AC⁰. Furthermore, we show that with 5 memory states and messages of length polylog(n) they can compute exactly the functions in the communication class PSPACE^cc. This gives the first meaningful characterization of PSPACE^cc in terms of space, originally defined in Babai, Frankl, and Simon 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.