## Abstract

Information complexity is the extension of classical information theory to the interactive setting, where instead of one-way transmission we are interested in back-and-forth communication. This approach has been very influential in communication complexity, where it enables us to prove powerful lower bounds by quantifying the amount of information the participants in the computation must reveal about their inputs. In this paper we study information complexity in the classical broadcast model: k parties with private inputs wish to compute some function of their inputs, and they communicate by sending messages (one at a time) over a broadcast channel. We measure how much information the players reveal about their inputs to an external observer. This is called external information cost. Using this approach, we prove a tight lower bound of Ω (n log k+ k) on the communication complexity of set disjointness, a fundamental problem in communication complexity. We also give a deterministic matching upper bound. Next we study compression, a central question in information complexity: given a protocol with low information cost (but possibly high communication), can we compress the protocol so that its communication cost matches its information cost? In the twoplayer setting, it is known that every protocol can be compressed to roughly its external information cost. We show that for the multi-party case this is no longer true: There is a gap of at least (k= log k) between external information and communication. However, if we wish to compress many independent instances of the same protocol, then it is possible to do so with an amortized percopy cost that approaches the information cost as the number of copies goes to infinity.

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

Title of host publication | PODC 2015 - Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing |

Publisher | Association for Computing Machinery |

Pages | 355-364 |

Number of pages | 10 |

ISBN (Electronic) | 9781450336178 |

DOIs | |

State | Published - Jul 21 2015 |

Externally published | Yes |

Event | ACM Symposium on Principles of Distributed Computing, PODC 2015 - Donostia-San Sebastian, Spain Duration: Jul 21 2015 → Jul 23 2015 |

### Publication series

Name | Proceedings of the Annual ACM Symposium on Principles of Distributed Computing |
---|---|

Volume | 2015-July |

### Other

Other | ACM Symposium on Principles of Distributed Computing, PODC 2015 |
---|---|

Country/Territory | Spain |

City | Donostia-San Sebastian |

Period | 7/21/15 → 7/23/15 |

## All Science Journal Classification (ASJC) codes

- Software
- Hardware and Architecture
- Computer Networks and Communications