A hard-to-compress interactive task?

Research output: Chapter in Book/Report/Conference proceedingConference contribution

8 Scopus citations

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.

Original languageEnglish (US)
Title of host publication2013 51st Annual Allerton Conference on Communication, Control, and Computing, Allerton 2013
PublisherIEEE Computer Society
Pages8-12
Number of pages5
ISBN (Print)9781479934096
DOIs
StatePublished - Jan 1 2013
Event51st Annual Allerton Conference on Communication, Control, and Computing, Allerton 2013 - Monticello, IL, United States
Duration: Oct 2 2013Oct 4 2013

Publication series

Name2013 51st Annual Allerton Conference on Communication, Control, and Computing, Allerton 2013

Other

Other51st Annual Allerton Conference on Communication, Control, and Computing, Allerton 2013
CountryUnited States
CityMonticello, IL
Period10/2/1310/4/13

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Control and Systems Engineering

Fingerprint Dive into the research topics of 'A hard-to-compress interactive task?'. Together they form a unique fingerprint.

  • Cite this

    Braverman, M. (2013). A hard-to-compress interactive task? In 2013 51st Annual Allerton Conference on Communication, Control, and Computing, Allerton 2013 (pp. 8-12). [6736498] (2013 51st Annual Allerton Conference on Communication, Control, and Computing, Allerton 2013). IEEE Computer Society. https://doi.org/10.1109/Allerton.2013.6736498