Capturing Multiparty Communication: Extending Notions of Information Theory to Topology-Dependent Multiparty Problems

Abstract

Multiparty communication is a natural paradigm for many applications in computer science and engineering, including distributed computing, smart robot communication, and data streaming algorithms. Two-party communication in the message passing model is fairly well understood; however, strong definitions of multiparty communication have been more elusive. Multiparty communication is further complicated by the existence of a network topology which defines how and when parties can communicate. In this project, we approach the problem of k-party communication over a network topology by reasoning about the relationship between the information complexity and communication complexity of the multiparty problem. In order to make information complexity and communication complexity of multiparty problems over graph networks more relatable and manipulable, we define them with respect to vertex cuts on the network graph, which induces two-party instances over the graph. We find that many of the notions of information complexity that are useful in the two-party setting also apply in multiparty settings. However, it seems that in relying on cuts for our reduction, we lose an inherent gap of O(log k) in a lower bound on communication complexity of the multiparty problem.