Title :
A hard-to-compress interactive task?
Author_Institution :
Dept. of Comput. Sci., Princeton Univ., Princeton, NJ, USA
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.
Keywords :
communication complexity; sampling methods; communication complexity; hard-to-compress interactive task; information complexity; interactive problem; sampling problem; Complexity theory; Computer science; Context; Educational institutions; Indexes; Protocols; Source coding;
Conference_Titel :
Communication, Control, and Computing (Allerton), 2013 51st Annual Allerton Conference on
Conference_Location :
Monticello, IL
Print_ISBN :
978-1-4799-3409-6
DOI :
10.1109/Allerton.2013.6736498
