@inproceedings{70ba6e41734f40f2a8ae9cea50762bfc,

title = "Interactive compression to external information",

abstract = "We describe a new way of compressing two-party communication protocols to get protocols with potentially smaller communication. We show that every communication protocol that communicates C bits and reveals I bits of information about the participants{\textquoteright} private inputs to an observer that watches the communication, can be simulated by a new protocol that communicates at most pol (I) · log log(C) bits. Our result is tight up to polynomial factors, as it matches the recent work separating communication complexity from external information cost.",

keywords = "Communication complexity, Correlated sampling, External information cost, Information theory, Interactive compression",

author = "Mark Braverman and Gillat Kol",

note = "Funding Information: Research supported in part by NSF Awards DMS-1128155 and CCF-1525342, a Packard Fellowship in Science and Engineering, and the Simons Collaboration on Algorithms and Geometry. †Research supported by National Science Foundation grant No. CCF-1750443.; 50th Annual ACM Symposium on Theory of Computing, STOC 2018 ; Conference date: 25-06-2018 Through 29-06-2018",

year = "2018",

month = jun,

day = "20",

doi = "10.1145/3188745.3188956",

language = "English (US)",

series = "Proceedings of the Annual ACM Symposium on Theory of Computing",

publisher = "Association for Computing Machinery",

pages = "760--772",

editor = "Monika Henzinger and David Kempe and Ilias Diakonikolas",

booktitle = "STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing",

}