文章基本信息

标题：Trading Information Complexity for Error
本地全文：下载
作者：Yuval Dagan ; Yuval Filmus ; Hamed Hatami 等
期刊名称：Theory of Computing
印刷版ISSN：1557-2862
电子版ISSN：1557-2862
出版年度：2018
卷号：14
页码：1-73
DOI：10.4086/toc.2018.v014a006
出版社：University of Chicago
摘要：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 ε. • For arbitrary functions, we obtain lower bounds and upper bounds indicating a gain that is of order Ω(h(ε)) and O(h( √ ε)), 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 Θ(h(ε)). 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 Θ( p h(ε)) 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.
关键词：communication complexity; information complexity