Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > PROTOCOL COMPRESSION:
Reports tagged with protocol compression:
TR16-081 | 20th May 2016
Alexander A. Sherstov

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 case when
the participants' inputs are distributed independently and show how to
compress the communication to $O(I\log^{2}I)$ bits, with ... more >>>




ISSN 1433-8092 | Imprint