### Abstract

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.

Original language | English (US) |
---|---|

Title of host publication | 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016 |

Editors | Yuval Rabani, Ioannis Chatzigiannakis, Davide Sangiorgi, Michael Mitzenmacher |

Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |

ISBN (Electronic) | 9783959770132 |

DOIs | |

State | Published - Aug 1 2016 |

Event | 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016 - Rome, Italy Duration: Jul 12 2016 → Jul 15 2016 |

### Publication series

Name | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|

Volume | 55 |

ISSN (Print) | 1868-8969 |

### Other

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

Country | Italy |

City | Rome |

Period | 7/12/16 → 7/15/16 |

### All Science Journal Classification (ASJC) codes

- Software

### Keywords

- Communication complexity
- Convergence rate
- Information complexity

## Cite this

Braverman, M., & Schneider, J. (2016). Information complexity is computable. In Y. Rabani, I. Chatzigiannakis, D. Sangiorgi, & M. Mitzenmacher (Eds.),

*43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016*[87] (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 55). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.ICALP.2016.87