文章基本信息

标题：Information Complexity Is Computable
本地全文：下载
作者：Mark Braverman ; Jon Schneider
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2016
卷号：55
页码：87:1-87:10
DOI：10.4230/LIPIcs.ICALP.2016.87
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：The information complexity of a function f is the minimum amount of information Alice and Bob need to exchange to compute the function f. In this paper we provide an algorithm for approximating the information complexity of an arbitrary function f to within any additive error epsilon > 0, thus resolving an open question as to whether information complexity is computable. In the process, we give the first explicit upper bound on the rate of convergence of the information complexity of f when restricted to b-bit protocols to the (unrestricted) information complexity of f.
关键词：Communication complexity; convergence rate; information complexity