Compressing Interactive Communication under Product Distributions

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.Non UBCUnreviewedAuthor affiliation: UCLAFacult