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].
@InProceedings{dagan_et_al:LIPIcs.CCC.2017.16, author = {Dagan, Yuval and Filmus, Yuval and Hatami, Hamed and Li, Yaqiao}, 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 = {O'Donnell, Ryan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2017.16}, URN = {urn:nbn:de:0030-drops-75179}, doi = {10.4230/LIPIcs.CCC.2017.16}, annote = {Keywords: communication complexity, information complexity} }
Feedback for Dagstuhl Publishing