Arunachalam, Srinivasan ;
Podder, Supartha
Communication Memento: Memoryless Communication Complexity
Abstract
We study the communication complexity of computing functions F: {0,1}ⁿ × {0,1}ⁿ → {0,1} in the memoryless communication model. Here, Alice is given x ∈ {0,1}ⁿ, Bob is given y ∈ {0,1}ⁿ and their goal is to compute F(x,y) subject to the following constraint: at every round, Alice receives a message from Bob and her reply to Bob solely depends on the message received and her 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 Alice and Bob (on the worst case input 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 quantum bits, only one player is allowed to send messages. We show that some of these different variants of our memoryless communication model capture the gardenhose model of computation by Buhrman et al. (ITCS'13), spacebounded communication complexity by Brody et al. (ITCS'13) and the overlay communication complexity by Papakonstantinou et al. (CCC'14). Thus the memoryless communication complexity model provides a unified framework to study all these spacebounded communication complexity models.
We establish the following main results: (1) We show that the memoryless communication complexity of F equals the logarithm of the size of the smallest bipartite branching program computing F (up to a factor 2); (2) We show that memoryless communication complexity equals gardenhose model of computation; (3) We exhibit various exponential separations between these memoryless communication models.
We end with an intriguing open question: can we find an explicit function F and universal constant c > 1 for which the memoryless communication complexity is at least c log n? Note that c ≥ 2+ε would imply a Ω(n^{2+ε}) lower bound for general formula size, improving upon the best lower bound by [Nečiporuk, 1966].
BibTeX  Entry
@InProceedings{arunachalam_et_al:LIPIcs.ITCS.2021.61,
author = {Srinivasan Arunachalam and Supartha Podder},
title = {{Communication Memento: Memoryless Communication Complexity}},
booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
pages = {61:161:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771771},
ISSN = {18688969},
year = {2021},
volume = {185},
editor = {James R. Lee},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13600},
URN = {urn:nbn:de:0030drops136007},
doi = {10.4230/LIPIcs.ITCS.2021.61},
annote = {Keywords: Communication complexity, space complexity, branching programs, gardenhose model, quantum computing}
}
04.02.2021
Keywords: 

Communication complexity, space complexity, branching programs, gardenhose model, quantum computing 
Seminar: 

12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

Issue date: 

2021 
Date of publication: 

04.02.2021 