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.|
|Electronic Publication Date:||13-Feb-2014|
|Citation:||Braverman, M. (2013). A hard-to-compress interactive task?. 8 - 12. 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|
Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.