Interactive Compression for Multi-Party Protocol

Authors Gillat Kol, Rotem Oshman, Dafna Sadeh



PDF
Thumbnail PDF

File

LIPIcs.DISC.2017.31.pdf
  • Filesize: 0.59 MB
  • 15 pages

Document Identifiers

Author Details

Gillat Kol
Rotem Oshman
Dafna Sadeh

Cite AsGet BibTex

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)
https://doi.org/10.4230/LIPIcs.DISC.2017.31

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.
Keywords
  • interactive compression
  • multi-party communication

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, and D. Sivakumar. An information statistics approach to data stream and communication complexity. J. Comput. Syst. Sci., 68(4):702-732, 2004. Google Scholar
  2. Boaz Barak, Mark Braverman, Xi Chen, and Anup Rao. How to compress interactive communication. In STOC, pages 67-76, 2010. Google Scholar
  3. Balthazar Bauer, Shay Moran, and Amir Yehudayoff. Internal compression of protocols to entropy. In APPROX/RANDOM, pages 481-496, 2015. Google Scholar
  4. Mark Braverman. Interactive information complexity. In STOC, pages 505-524, 2012. Google Scholar
  5. Mark Braverman and Rotem Oshman. On information complexity in the broadcast model. In PODC, pages 355-364, 2015. Google Scholar
  6. Mark Braverman and Anup Rao. Information equals amortized communication. In FOCS, pages 748-757, 2011. Google Scholar
  7. Joshua Brody, Harry Buhrman, Michal Koucký, Bruno Loff, Florian Speelman, and Nikolay K. Vereshchagin. Towards a reverse newman’s theorem in interactive information complexity. In CCC, pages 24-33, 2013. Google Scholar
  8. Amit Chakrabarti, Yaoyun Shi, Anthony Wirth, and Andrew Chi-Chih Yao. Informational complexity and the direct sum problem for simultaneous message complexity. In FOCS, pages 270-278, 2001. Google Scholar
  9. Robert M Fano. The transmission of information. Massachusetts Institute of Technology, Research Laboratory of Electronics, 1949. Google Scholar
  10. Prahladh Harsha, Rahul Jain, David A. McAllester, and Jaikumar Radhakrishnan. The communication complexity of correlation. IEEE Transactions on Information Theory, 56(1):438-449, 2010. Google Scholar
  11. David A Huffman. A method for the construction of minimum redundancy codes. proc. IRE, 40(9):1098-1101, 1952. Google Scholar
  12. Gillat Kol. Interactive compression for product distributions. In STOC, pages 987-998, 2016. Google Scholar
  13. Gillat Kol and Ran Raz. Interactive channel capacity. In STOC, pages 715-724, 2013. Google Scholar
  14. Sivaramakrishnan Natarajan Ramamoorthy and Anup Rao. How to compress asymmetric communication. In CCC, pages 102-123, 2015. Google Scholar
  15. C. E. Shannon. A mathematical theory of communication. The Bell Systems Technical Journal, 27:July 379-423, October 623-656, 1948. Google Scholar
  16. Alexander A. Sherstov. Compressing interactive communication under product distributions. In FOCS, pages 535-544, 2016. Google Scholar
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