Prahladh Harsha, Rahul Jain, Jaikumar Radhakrishnan

Let $f : \{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1\}$ be a 2-party function. For every product distribution $\mu$ on $\{0,1\}^n \times \{0,1\}^n$, we show that $${{CC}}^\mu_{0.49}(f) = O\left(\left(\log {{rprt}}_{1/4}(f) \cdot \log \log {{rprt}}_{1/4}(f)\right)^2\right),$$ where ${{CC}^\mu_\varepsilon(f)$ is the distributional communication complexity with error at most $\varepsilon$ under the distribution $\mu$ and ... more >>>

Alexander A. Sherstov

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 >>>