Abstract
We consider the standard twoparty 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 twobit 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 priorfree 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 epsilonerror 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:116:59},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770408},
ISSN = {18688969},
year = {2017},
volume = {79},
editor = {Ryan O'Donnell},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7517},
URN = {urn:nbn:de:0030drops75179},
doi = {10.4230/LIPIcs.CCC.2017.16},
annote = {Keywords: communication complexity, information complexity}
}
Keywords: 

communication complexity, information complexity 
Seminar: 

32nd Computational Complexity Conference (CCC 2017) 
Issue Date: 

2017 
Date of publication: 

21.07.2017 