Interactive compression for multi-party protocols

Gillat Kol, Rotem Oshman, Dafna Sadeh

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

The 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 κ players, one can compress protocols down to Õ(I ·κ), where I is the information content of the protocol and κ is the number of players. We complement this result with an almost matching lower bound of Ω(I κ), which shows that a nearly-linear dependence on the number of players cannot be avoided.

Original languageEnglish (US)
Title of host publication31st International Symposium on Distributed Computing, DISC 2017
EditorsAndrea W. Richa
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770538
DOIs
StatePublished - Oct 1 2017
Event31st International Symposium on Distributed Computing, DISC 2017 - Vienna, Austria
Duration: Oct 16 2017Oct 20 2017

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume91
ISSN (Print)1868-8969

Other

Other31st International Symposium on Distributed Computing, DISC 2017
CountryAustria
CityVienna
Period10/16/1710/20/17

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Interactive compression
  • Multi-party communication

Fingerprint Dive into the research topics of 'Interactive compression for multi-party protocols'. Together they form a unique fingerprint.

  • Cite this

    Kol, G., Oshman, R., & Sadeh, D. (2017). Interactive compression for multi-party protocols. In A. W. Richa (Ed.), 31st International Symposium on Distributed Computing, DISC 2017 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 91). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.DISC.2017.31