@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 = "Publisher Copyright: {\textcopyright} 2018 Copyright held by the owner/author(s).; 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",
}