A hard-to-compress interactive task?

摘要

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.