Interactive channel capacity

We study the interactive channel capacity of an ε-noisy channel. The interactive channel capacity C(ε) is defined as the minimal ratio between the communication complexity of a problem (over a non-noisy channel), and the communication complexity of the same problem over the binary symmetric channel with noise rate ε, where the communication complexity tends to infinity.

Authors

• Gillat Kol
• Ran Raz

Keywords

• communication complexity
• the entropy function
• interactive channel capacity
• information theory