Skip to main content

Interactive Compression for Multi-Party Protocol

Author(s): Kol, Gillat; Oshman, Rotem; Sadeh, Dafna

Download
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1pc0s
Full metadata record
DC FieldValueLanguage
dc.contributor.authorKol, Gillat-
dc.contributor.authorOshman, Rotem-
dc.contributor.authorSadeh, Dafna-
dc.date.accessioned2021-10-08T19:46:49Z-
dc.date.available2021-10-08T19:46:49Z-
dc.date.issued2017en_US
dc.identifier.citationKol, Gillat, Rotem Oshman, and Dafna Sadeh. "Interactive Compression for Multi-Party Protocol." In 31st International Symposium on Distributed Computing (DISC) (2017): pp. 31:1-31:15. doi:10.4230/LIPIcs.DISC.2017.31en_US
dc.identifier.issn1868-8969-
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/pr1pc0s-
dc.description.abstractThe field of compression studies the question of how many bits of communication are necessary to convey a given piece of data. For one-way communication between a sender and a receiver, the seminal work of Shannon and Huffman showed that the communication required is characterized by the entropy of the data; in recent years, there has been a great amount of interest in extending this line of research to interactive communication, where instead of a sender and a receiver we have two parties communication back-and-forth. In this paper we initiate the study of interactive compression for distributed multi-player protocols. We consider the classical shared blackboard model, where players take turns speaking, and each player's message is immediately seen by all the other players. We show that in the shared blackboard model with k players, one can compress protocols down to ~O(Ik), where I is the information content of the protocol and k is the number of players. We complement this result with an almost matching lower bound of ~Omega(Ik), which shows that a nearly-linear dependence on the number of players cannot be avoided.en_US
dc.format.extent31:1 - 31:15en_US
dc.language.isoen_USen_US
dc.relation.ispartof31st International Symposium on Distributed Computingen_US
dc.rightsFinal published version. This is an open access article.en_US
dc.titleInteractive Compression for Multi-Party Protocolen_US
dc.typeConference Articleen_US
dc.identifier.doi10.4230/LIPIcs.DISC.2017.31-
pu.type.symplectichttp://www.symplectic.co.uk/publications/atom-terms/1.0/conference-proceedingen_US

Files in This Item:
File Description SizeFormat 
InteractiveCompressionMultiPartyProtocols.pdf609.02 kBAdobe PDFView/Download


Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.