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.