License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2017.16
URN: urn:nbn:de:0030-drops-75179
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7517/
Go to the corresponding LIPIcs Volume Portal

Dagan, Yuval ; Filmus, Yuval ; Hatami, Hamed ; Li, Yaqiao

Trading Information Complexity for Error

pdf-format:
LIPIcs-CCC-2017-16.pdf (0.8 MB)

Abstract

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

* 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})). 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. [Braverman, STOC 2013].

* 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 of question of Braverman et al. regarding the randomized communication complexity of the set disjointness function.

* Answering a question of Braverman [Braverman, STOC 2012], 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 light of [Braverman, STOC 2012], this implies that 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[C_{DISJ} - Theta(h(epsilon))] + o(n), where C_{DISJ} ~ 0.4827$ is the constant found by Braverman et al. [Braverman, STOC 2012].

BibTeX - Entry

@InProceedings{dagan_et_al:LIPIcs:2017:7517,
  author =	{Yuval Dagan and Yuval Filmus and Hamed Hatami and Yaqiao Li},
  title =	{{Trading Information Complexity for Error}},
  booktitle =	{32nd Computational Complexity Conference (CCC 2017)},
  pages =	{16:1--16:59},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-040-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{79},
  editor =	{Ryan O'Donnell},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7517},
  URN =		{urn:nbn:de:0030-drops-75179},
  doi =		{10.4230/LIPIcs.CCC.2017.16},
  annote =	{Keywords: communication complexity, information complexity}
}

Keywords: communication complexity, information complexity
Collection: 32nd Computational Complexity Conference (CCC 2017)
Issue Date: 2017
Date of publication: 01.08.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI