Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR15-168 | 18th October 2015 23:41

#### Interactive Compression for Product Distributions

TR15-168
Authors: Gillat Kol
Publication: 18th October 2015 23:51
We study the interactive compression problem: Given a two-party communication protocol with small information cost, can it be compressed so that the total number of bits communicated is also small? We consider the case where the parties have inputs that are independent of each other, and give a simulation protocol that communicates $I^2 \cdot polylog(I)$ bits, where $I$ is the information cost of the original protocol. Our protocol is the first simulation protocol whose communication complexity is bounded by a polynomial in the information cost of the original protocol.