Skip to main content

A hard-to-compress interactive task?

Author(s): Braverman, Mark

To refer to this page use:
Abstract: Whether the information complexity of any interactive problem is close to its communication complexity is an important open problem. In this note we give an example of a sampling problem whose information and communication complexity we conjecture to be as much as exponentially far apart.
Publication Date: 2-Oct-2013
Electronic Publication Date: 13-Feb-2014
Citation: Braverman, M. (2013). A hard-to-compress interactive task?. 8 - 12. doi:10.1109/Allerton.2013.6736498
DOI: doi:10.1109/Allerton.2013.6736498
Pages: 8 - 12
Type of Material: Conference Article
Journal/Proceeding Title: 51st Annual Allerton Conference on Communication, Control, and Computing, Allerton 2013
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.