Does the information complexity of a function equal its communication complexity? We examine whether any currently known techniques might be used to show a separation between the two notions. Recently, Ganor et al. provided such a separation in the distributional setting for a specific input distribution ?. We show that ... more >>>

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