1 Search Results for "Sadeh, Dafna"

Document
DOI: 10.4230/LIPIcs.DISC.2017.31
Interactive Compression for Multi-Party Protocol

Authors: Gillat Kol, Rotem Oshman, and Dafna Sadeh

Published in: LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017)

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 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.
Cite as

Gillat Kol, Rotem Oshman, and Dafna Sadeh. Interactive Compression for Multi-Party Protocol. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 31:1-31:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{kol_et_al:LIPIcs.DISC.2017.31,
  author =	{Kol, Gillat and Oshman, Rotem and Sadeh, Dafna},
  title =	{{Interactive Compression for Multi-Party Protocol}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{31:1--31:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Richa, Andr\'{e}a},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.31},
  URN =		{urn:nbn:de:0030-drops-80111},
  doi =		{10.4230/LIPIcs.DISC.2017.31},
  annote =	{Keywords: interactive compression, multi-party communication}
}
  • Refine by Author
  • 1 Kol, Gillat
  • 1 Oshman, Rotem
  • 1 Sadeh, Dafna

  • Refine by Classification

  • Refine by Keyword
  • 1 interactive compression
  • 1 multi-party communication

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2017

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact