Volume 14 (2018) Article 6 pp. 1-73
CCC 2017 Special Issue

Trading Information Complexity for Error

by Yuval Dagan, Yuval Filmus, Hamed Hatami, and Yaqiao Li

Received: June 2, 2017
Revised: April 16, 2018
Published: May 15, 2018

$ \newcommand{\CDISJ}{\mathsf{CDISJ}} $

We consider the standard two-party communication model. The central problem studied in this article is how much one can save in information complexity by allowing an error of $\epsilon$.

• For arbitrary functions, we obtain lower bounds and upper bounds indicating a gain that is of order $\Omega(h(\epsilon))$ and $O(h(\sqrt{\epsilon}))$, respectively. Here $h$ denotes the binary entropy function.
• We analyze the case of the two-bit AND function in detail to show that for this function the gain is $\Theta(h(\epsilon))$. This answers a question of Braverman et al (STOC'13).
• We obtain sharp bounds for the set disjointness function of order $n$. For the case of the distributional error, we introduce a new protocol that achieves a gain of $\Theta(\sqrt{h(\epsilon)})$ provided that $n$ is sufficiently large. We apply these results to answer another question of Braverman et al. regarding the randomized communication complexity of the set disjointness function.
• Answering a question of Braverman (STOC'12), we apply our analysis of the set disjointness function to establish a gap between the two different notions of the prior-free information cost. In the light of Braverman (STOC'12), this implies that the amortized randomized communication complexity is not necessarily equal to the amortized distributional communication complexity with respect to the hardest distribution.

As a consequence, we show that the $\epsilon$-error randomized communication complexity of the set disjointness function of order $n$ is $n[\CDISJ - \Theta(h(\epsilon))] + o(n)$, where $\CDISJ \approx 0.4827$ is the constant found by Braverman et al. (STOC'13).

A conference version of this paper appeared in the Proceedings of the 32nd IEEE Conference on Computational Complexity, 2017.

DOI: 10.4086/toc.2018.v014a006

© 2018 Yuval Dagan, Yuval Filmus, Hamed Hatami, and Yaqiao Li
Licensed under a Creative Commons Attribution License (CC-BY)