Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR15-168 | 18th October 2015 23:41

Interactive Compression for Product Distributions

RSS-Feed




TR15-168
Authors: Gillat Kol
Publication: 18th October 2015 23:51
Downloads: 2126
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint