TY - GEN

T1 - Information complexity is computable

AU - Braverman, Mark

AU - Schneider, Jon

N1 - Funding Information:
Research supported in part by an NSF CAREER award (CCF-1149888), NSF CCF-1525342, a Packard Fellowship in Science and Engineering, and the Simons Collaboration on Algorithms and Geometry

PY - 2016/8/1

Y1 - 2016/8/1

N2 - 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 ϵ > 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.

AB - 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 ϵ > 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.

KW - Communication complexity

KW - Convergence rate

KW - Information complexity

UR - http://www.scopus.com/inward/record.url?scp=85012901487&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85012901487&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.ICALP.2016.87

DO - 10.4230/LIPIcs.ICALP.2016.87

M3 - Conference contribution

AN - SCOPUS:85012901487

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016

A2 - Rabani, Yuval

A2 - Chatzigiannakis, Ioannis

A2 - Sangiorgi, Davide

A2 - Mitzenmacher, Michael

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016

Y2 - 12 July 2016 through 15 July 2016

ER -