### Abstract

We show an exponential gap between communication complexity and information complexity for boolean functions, by giving an explicit example of a partial function with information complexity ≤ O(k), and distributional communication complexity ≥ 2^{k}. This shows that a communication protocol for a partial boolean function cannot always be compressed to its internal information. By a result of Braverman [3], our gap is the largest possible. By a result of Braverman and Rao [4], our example shows a gap between communication complexity and amortized communication complexity, implying that a tight direct sum result for distributional communication complexity of boolean functions cannot hold, answering a long standing open problem. Our techniques build on [13], that proved a similar result for relations with very long outputs (double exponentially long in k). In addition to the stronger result, the current work gives a simpler proof, benefiting from the short output length of boolean functions. Another (conceptual) contribution of our work is the relative discrepancy method, a new rectangle-based method for proving communication complexity lower bounds for boolean functions, powerful enough to separate information complexity and communication complexity.

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

Title of host publication | STOC 2015 - Proceedings of the 2015 ACM Symposium on Theory of Computing |

Publisher | Association for Computing Machinery |

Pages | 557-566 |

Number of pages | 10 |

ISBN (Electronic) | 9781450335362 |

DOIs | |

State | Published - Jun 14 2015 |

Externally published | Yes |

Event | 47th Annual ACM Symposium on Theory of Computing, STOC 2015 - Portland, United States Duration: Jun 14 2015 → Jun 17 2015 |

### Publication series

Name | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|

Volume | 14-17-June-2015 |

ISSN (Print) | 0737-8017 |

### Other

Other | 47th Annual ACM Symposium on Theory of Computing, STOC 2015 |
---|---|

Country | United States |

City | Portland |

Period | 6/14/15 → 6/17/15 |

### All Science Journal Classification (ASJC) codes

- Software

### Keywords

- Amortized communication complexity
- Communication complexity
- Communication compression
- Direct sum
- Information complexity

## Fingerprint Dive into the research topics of 'Exponential separation of information and communication for boolean functions'. Together they form a unique fingerprint.

## Cite this

*STOC 2015 - Proceedings of the 2015 ACM Symposium on Theory of Computing*(pp. 557-566). (Proceedings of the Annual ACM Symposium on Theory of Computing; Vol. 14-17-June-2015). Association for Computing Machinery. https://doi.org/10.1145/2746539.2746572