Open Collections

Compressing Interactive Communication under Product Distributions

Banff International Research Station for Mathematical Innovation and Discovery

We study the problem of compressing interactive communication to its information content I, defined as the amount of information that the participants learn about each other's inputs. We focus on the canonical setting where the participants' inputs are distributed independently and show how to compress the communication to O(I log2 I) bits, with no dependence on the original communication cost. This result essentially matches the well-known lower bound of Ω(I) and improves quadratically on previous work (Kol, STOC 2016). Our result complements the recent breakthrough of Ganor, Kol, and Raz (STOC 2014 and FOCS 2015), who show that one cannot achieve compression better than exp(Θ(I)) in the general case when the participants' inputs are dependent random variables.

Mathematics; Computer science; Information and communication, circuits; Theoretical computer science

video/mp4

Author affiliation: UCLA

2017-09-18

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/63061

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/