To refer to this page use:
http://arks.princeton.edu/ark:/88435/pr1cw93
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.