Interactive compression for product distributions

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

10 Scopus citations

Abstract

We study the interactive compression problem: Given a two-party communication protocol with small information cost, can it be compressed so that the total number of bits communicated is also small? We consider the case where the parties have inputs that are independent of each other, and give a simulation protocol that communicates I2 · polylog(I) bits, where I is the information cost of the original protocol. Our protocol is the first simulation protocol whose communication complexity is bounded by a polynomial in the information cost of the original protocol.

Original languageEnglish (US)
Title of host publicationSTOC 2016 - Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing
EditorsYishay Mansour, Daniel Wichs
PublisherAssociation for Computing Machinery
Pages987-998
Number of pages12
ISBN (Electronic)9781450341325
DOIs
StatePublished - Jun 19 2016
Externally publishedYes
Event48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016 - Cambridge, United States
Duration: Jun 19 2016Jun 21 2016

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
Volume19-21-June-2016
ISSN (Print)0737-8017

Other

Other48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016
CountryUnited States
CityCambridge
Period6/19/166/21/16

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Communication complexity
  • Information complexity
  • Information theory
  • Interactive compression

Fingerprint Dive into the research topics of 'Interactive compression for product distributions'. Together they form a unique fingerprint.

  • Cite this

    Kol, G. (2016). Interactive compression for product distributions. In Y. Mansour, & D. Wichs (Eds.), STOC 2016 - Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing (pp. 987-998). (Proceedings of the Annual ACM Symposium on Theory of Computing; Vol. 19-21-June-2016). Association for Computing Machinery. https://doi.org/10.1145/2897518.2897537