Communication memento: Memoryless communication complexity

Abstract

We study the communication complexity of computing functions $F:\{0,1\}^n \times \{0,1\}^n\rightarrow \{0,1\}$ in the memoryless communication model. Here, Alice and Bob are given $x\in \{0,1\}^n$, $y\in \{0,1\}^n$ respectively and their goal is to compute $F(x,y)$ subject to the constraint: at every round, Alice receives a message from Bob and her reply to Bob solely depends on the message received and input $x$ (in particular, her reply is independent of the information from the previous rounds); the same applies to Bob. The cost of computing $F$ in this model is the maximum number of bits exchanged in any round between them (on the hardest inputs $x,y$). In this paper, we also consider variants of our memoryless model wherein one party is allowed to have memory, the parties are allowed to communicate qubits, only one player is allowed to send messages and the relationship between our model and the garden-hose model of computation. Restricted versions of our communication model were studied before by Brody et al. (ITCS'13) and Papakonstantinou et al. (CCC'14), in the context of space-bounded communication complexity. In this paper, we establish following: (1) We show that the memoryless communication complexity of $F$ characterizes the logarithm of the size of the smallest bipartite branching program computing $F$ (up to a factor 2); (2) We give exponential separations between the classical variants of memoryless communication models; (3) We exhibit exponential quantum-classical separations in the four variants of the memoryless communication model. We end with an intriguing open question: can we find an explicit $F$ and constant c>1 for which the memoryless communication complexity is at least $c \log n$? Note that $c\geq 2+\varepsilon$ would imply a $\Omega(n^{2+\varepsilon})$ lower bound for general formula size, improving upon the best lower bound by Neciporuk [Nec66].