Measuring communication complexity using instance complexity with oracles

Armando Matos, Andreia Teixeira, Andre Souto

We establish a connection between non-deterministic communication complexity and instance complexity, a measure of information based on algorithmic entropy. Let $\overline{x}$, $\o…