Dagan, Yuval ;
Filmus, Yuval ;
Hatami, Hamed ;
Li, Yaqiao
Trading Information Complexity for Error
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}
}
2017
Keywords: 

communication complexity, information complexity 
Seminar: 

32nd Computational Complexity Conference (CCC 2017)

Issue date: 

2017 
Date of publication: 

2017 