Skip navigation
Please use this identifier to cite or link to this item:
Title: Capturing Multiparty Communication: Extending Notions of Information Theory to Topology-Dependent Multiparty Problems
Authors: Rolf, Esther
Advisors: Braverman, Mark
Contributors: Oshman, Rotem
Department: Computer Science
Class Year: 2016
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.
Extent: 57 pages
Type of Material: Princeton University Senior Theses
Language: en_US
Appears in Collections:Computer Science, 1988-2016

Files in This Item:
File SizeFormat 
Rolf_Esther_2016_Thesis.pdf385.55 kBAdobe PDF    Request a copy

Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.