### Abstract

We study the interactive compression problem: Given a two-party communication protocol with small information cost, can it be compressed so that the total number of bits communicated is also small? We consider the case where the parties have inputs that are independent of each other, and give a simulation protocol that communicates I^{2} · polylog(I) bits, where I is the information cost of the original protocol. Our protocol is the first simulation protocol whose communication complexity is bounded by a polynomial in the information cost of the original protocol.

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

Title of host publication | STOC 2016 - Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing |

Editors | Yishay Mansour, Daniel Wichs |

Publisher | Association for Computing Machinery |

Pages | 987-998 |

Number of pages | 12 |

ISBN (Electronic) | 9781450341325 |

DOIs | |

State | Published - Jun 19 2016 |

Externally published | Yes |

Event | 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016 - Cambridge, United States Duration: Jun 19 2016 → Jun 21 2016 |

### Publication series

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

Volume | 19-21-June-2016 |

ISSN (Print) | 0737-8017 |

### Other

Other | 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016 |
---|---|

Country | United States |

City | Cambridge |

Period | 6/19/16 → 6/21/16 |

### All Science Journal Classification (ASJC) codes

- Software

### Keywords

- Communication complexity
- Information complexity
- Information theory
- Interactive compression

## Fingerprint Dive into the research topics of 'Interactive compression for product distributions'. Together they form a unique fingerprint.

## Cite this

Kol, G. (2016). Interactive compression for product distributions. In Y. Mansour, & D. Wichs (Eds.),

*STOC 2016 - Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing*(pp. 987-998). (Proceedings of the Annual ACM Symposium on Theory of Computing; Vol. 19-21-June-2016). Association for Computing Machinery. https://doi.org/10.1145/2897518.2897537