Interactive compression to external information

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 ) · loglog( C ) bits. Our result is tight up to polynomial factors, as it matches the recent work separating communication complexity from external information cost.

Authors

• Mark Braverman
• Gillat Kol

Keywords

• Communication complexity
• Correlated sampling
• External information cost
• Information theory
• Interactive compression