Biblio
Filters: Keyword is Correlated sampling [Clear All Filters]
Interactive Compression to External Information. Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. :964-977.
.
2018. 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' private inputs to an observer that watches the communication, can be simulated by a new protocol that communicates at most poly(I) $\cdot$ loglog(C) bits. Our result is tight up to polynomial factors, as it matches the recent work separating communication complexity from external information cost.