Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

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

#### Interactive Channel Capacity

Revision #1
Authors: Gillat Kol, Ran Raz
Accepted on: 8th April 2013 18:02
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
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