ECCC-Report TR15-168https://eccc.weizmann.ac.il/report/2015/168Comments and Revisions published for TR15-168en-usSun, 18 Oct 2015 23:51:42 +0300
Paper TR15-168
| Interactive Compression for Product Distributions |
Gillat Kol
https://eccc.weizmann.ac.il/report/2015/168We 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.Sun, 18 Oct 2015 23:51:42 +0300https://eccc.weizmann.ac.il/report/2015/168