ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR13-001 | 8th April 2013 18:02

Interactive Channel Capacity

RSS-Feed




Revision #1
Authors: Gillat Kol, Ran Raz
Accepted on: 8th April 2013 18:02
Downloads: 273
Keywords: 


Abstract:

We 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.


Paper:

TR13-001 | 2nd January 2013 01:55

Interactive Channel Capacity





TR13-001
Authors: Gillat Kol, Ran Raz
Publication: 2nd January 2013 01:58
Downloads: 786
Keywords: 


Abstract:

We 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.



ISSN 1433-8092 | Imprint