A hard-to-compress interactive task?

Mark Braverman

doi:10.1109/Allerton.2013.6736498

A hard-to-compress interactive task?

Mark Braverman

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English (US)
Title of host publication	2013 51st Annual Allerton Conference on Communication, Control, and Computing, Allerton 2013
Publisher	IEEE Computer Society
Pages	8-12
Number of pages	5
ISBN (Print)	9781479934096
DOIs	https://doi.org/10.1109/Allerton.2013.6736498
State	Published - 2013
Externally published	Yes
Event	51st Annual Allerton Conference on Communication, Control, and Computing, Allerton 2013 - Monticello, IL, United States Duration: Oct 2 2013 → Oct 4 2013

Publication series

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

Other

Other	51st Annual Allerton Conference on Communication, Control, and Computing, Allerton 2013
Country/Territory	United States
City	Monticello, IL
Period	10/2/13 → 10/4/13

All Science Journal Classification (ASJC) codes

Computer Networks and Communications
Control and Systems Engineering

Access to Document

10.1109/Allerton.2013.6736498

Cite this

@inproceedings{ab6ae7307c794e77909b0af780b09226,

title = "A hard-to-compress interactive task?",

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.",

author = "Mark Braverman",

year = "2013",

doi = "10.1109/Allerton.2013.6736498",

language = "English (US)",

isbn = "9781479934096",

series = "2013 51st Annual Allerton Conference on Communication, Control, and Computing, Allerton 2013",

publisher = "IEEE Computer Society",

pages = "8--12",

booktitle = "2013 51st Annual Allerton Conference on Communication, Control, and Computing, Allerton 2013",

address = "United States",

note = "51st Annual Allerton Conference on Communication, Control, and Computing, Allerton 2013 ; Conference date: 02-10-2013 Through 04-10-2013",

}

Braverman, M 2013, A hard-to-compress interactive task? in 2013 51st Annual Allerton Conference on Communication, Control, and Computing, Allerton 2013., 6736498, 2013 51st Annual Allerton Conference on Communication, Control, and Computing, Allerton 2013, IEEE Computer Society, pp. 8-12, 51st Annual Allerton Conference on Communication, Control, and Computing, Allerton 2013, Monticello, IL, United States, 10/2/13. https://doi.org/10.1109/Allerton.2013.6736498

A hard-to-compress interactive task? / Braverman, Mark.
2013 51st Annual Allerton Conference on Communication, Control, and Computing, Allerton 2013. IEEE Computer Society, 2013. p. 8-12 6736498 (2013 51st Annual Allerton Conference on Communication, Control, and Computing, Allerton 2013).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution