2026-08-06T03:40:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6220 2024-03-06T10:37:49Z ddc:004 open_access

Information Complexity Is Computable Braverman, Mark Schneider, Jon Communication complexity convergence rate information complexity 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mark Braverman and Jon Schneider 2016 Is Part Of LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2016.87 urn:nbn:de:0030-drops-62203 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.87 eng https://creativecommons.org/licenses/by/3.0/legalcode