A hard-to-compress interactive task?

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

11 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 - 2013
Externally publishedYes
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
Country/TerritoryUnited 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