文章基本信息

标题：Trading information complexity for error
本地全文：下载
作者：Yuval Dagan ; Yuval Filmus ; Hamed Hatami 等
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2016
卷号：2016
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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 ( )) . 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 [M. Braverman, A. Garg, D. Pankratov, and O. Weinstein, From information to exact communication (extended abstract), 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 ( h ( ) ) 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 [Mark Braverman, Interactive information complexity, STOC'12], we apply our analysis of the set disjointness function to establish a gap between the two different notions of the prior-free information cost. This implies that amortized randomized communication complexity is not necessarily equal to the amortized distributional communication complexity with respect to the hardest distribution.
关键词：information complexity ; Set disjointness problem