1 Department of Computer Science, Science and Technology, Aarhus University2 Tsinghua University3 Chinese Academy of Sciences4 Department of Computer Science, Science and Technology, Aarhus University
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 communication is one-way, from Alice to Bob, where Bob controls two types of memory: (i) a large, oblivious memory, where updates are only a function of the received bit and the current memory content, and (ii) a smaller, non-oblivious/general memory, where updates can be a function of the input given to Bob. We exhibit natural protocols where this semi-obliviousness shows up. For this model we also introduce new techniques through which certain limitations of space-bounded computation are revealed. One of the main motivations of this work is in understanding the difference in the use of space when computing the following functions: Equality (EQ), Inner Product (IP), and connectivity in a directed graph (REACH). When viewed as communication problems, EQ can be decided using 0 non-oblivious bits (and log2 n oblivious bits), IP requires exactly 1 non-oblivious bit, whereas for REACH we obtain the same lower bound as for IP and conjecture that the actual bound is Omega(log2 n). In fact, proving that 1 non-oblivious bit is required becomes technically sophisticated, and the question even for 2 non-oblivious bits for any explicit boolean function remains open.
Proceedings of the 4th Conference on Innovations in Theoretical Computer Science , Itcs '13, 2013, p. 159-172
Main Research Area:
Conference on Innovations in Theoretical Computer ScienceInnovations in Theoretical Computer Science, 2013