Skip navigation
Please use this identifier to cite or link to this item: http://arks.princeton.edu/ark:/88435/dsp01q524jr208
 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 URI: http://arks.princeton.edu/ark:/88435/dsp01q524jr208 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

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