A hard-to-compress interactive task?
Mark Braverman · 2013
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.