On information complexity in the broadcast model

Mark Braverman, Rotem Oshman

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

10 Scopus citations

Abstract

Information complexity is the extension of classical information theory to the interactive setting, where instead of one-way transmission we are interested in back-and-forth communication. This approach has been very influential in communication complexity, where it enables us to prove powerful lower bounds by quantifying the amount of information the participants in the computation must reveal about their inputs. In this paper we study information complexity in the classical broadcast model: k parties with private inputs wish to compute some function of their inputs, and they communicate by sending messages (one at a time) over a broadcast channel. We measure how much information the players reveal about their inputs to an external observer. This is called external information cost. Using this approach, we prove a tight lower bound of Ω (n log k+ k) on the communication complexity of set disjointness, a fundamental problem in communication complexity. We also give a deterministic matching upper bound. Next we study compression, a central question in information complexity: given a protocol with low information cost (but possibly high communication), can we compress the protocol so that its communication cost matches its information cost? In the twoplayer setting, it is known that every protocol can be compressed to roughly its external information cost. We show that for the multi-party case this is no longer true: There is a gap of at least (k= log k) between external information and communication. However, if we wish to compress many independent instances of the same protocol, then it is possible to do so with an amortized percopy cost that approaches the information cost as the number of copies goes to infinity.

Original languageEnglish (US)
Title of host publicationPODC 2015 - Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing
PublisherAssociation for Computing Machinery
Pages355-364
Number of pages10
ISBN (Electronic)9781450336178
DOIs
StatePublished - Jul 21 2015
EventACM Symposium on Principles of Distributed Computing, PODC 2015 - Donostia-San Sebastian, Spain
Duration: Jul 21 2015Jul 23 2015

Publication series

NameProceedings of the Annual ACM Symposium on Principles of Distributed Computing
Volume2015-July

Other

OtherACM Symposium on Principles of Distributed Computing, PODC 2015
CountrySpain
CityDonostia-San Sebastian
Period7/21/157/23/15

All Science Journal Classification (ASJC) codes

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'On information complexity in the broadcast model'. Together they form a unique fingerprint.

  • Cite this

    Braverman, M., & Oshman, R. (2015). On information complexity in the broadcast model. In PODC 2015 - Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (pp. 355-364). (Proceedings of the Annual ACM Symposium on Principles of Distributed Computing; Vol. 2015-July). Association for Computing Machinery. https://doi.org/10.1145/2767386.2767425