ECCC-Report TR13-001https://eccc.weizmann.ac.il/report/2013/001Comments and Revisions published for TR13-001en-usMon, 08 Apr 2013 18:02:51 +0300
Revision 1
| Interactive Channel Capacity |
Gillat Kol,
Ran Raz
https://eccc.weizmann.ac.il/report/2013/001#revision1We study the interactive channel capacity of an $\epsilon$-noisy channel. The interactive channel capacity $C(\epsilon)$ 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 $\epsilon$, where the communication complexity tends to infinity.
Our main result is the upper bound $C(\epsilon) \leq 1-\Omega\left(\sqrt{H(\epsilon)}\right).$ This compares with Shannon's non-interactive channel capacity of $1-H(\epsilon)$. In particular, for a small enough $\epsilon$, our result gives the first separation between interactive and non-interactive channel capacity, answering an open problem by Schulman.
We complement this result by the lower bound $C(\epsilon) \geq 1-O\left(\sqrt{H(\epsilon)}\right),$ proved for the case where the players take alternating turns.Mon, 08 Apr 2013 18:02:51 +0300https://eccc.weizmann.ac.il/report/2013/001#revision1
Paper TR13-001
| Interactive Channel Capacity |
Gillat Kol,
Ran Raz
https://eccc.weizmann.ac.il/report/2013/001We study the interactive channel capacity of an $\epsilon$-noisy channel. The interactive channel capacity $C(\epsilon)$ 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 $\epsilon$, where the communication complexity tends to infinity.
Our main result is the upper bound $C(\epsilon) \leq 1-\Omega\left(\sqrt{H(\epsilon)}\right).$ This compares with Shannon's non-interactive channel capacity of $1-H(\epsilon)$. In particular, for a small enough $\epsilon$, our result gives the first separation between interactive and non-interactive channel capacity, answering an open problem by Schulman.
We complement this result by the lower bound $C(\epsilon) \geq 1-O\left(\sqrt{H(\epsilon)}\right),$ proved for the case where the players take alternating turns.Wed, 02 Jan 2013 01:58:50 +0200https://eccc.weizmann.ac.il/report/2013/001