TY - GEN

T1 - Interactive channel capacity

AU - Kol, Gillat

AU - Raz, Ran

PY - 2013

Y1 - 2013

N2 - 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 com- plexity tends to infinity. Our main result is the upper bound C(ε) ≤ 1-Ω (√H(ε) ) : This compares with Shannon's non-interactive channel ca- pacity of 1 - H(ε). In particular, for a small enough ε, our result gives the first separation between interactive and non- interactive channel capacity, answering an open problem by Schulman [6]. We complement this result by the lower bound C(ε) ≥ 1-O (√H(ε) ) ; proved for the case where the players take alternating turns.

AB - 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 com- plexity tends to infinity. Our main result is the upper bound C(ε) ≤ 1-Ω (√H(ε) ) : This compares with Shannon's non-interactive channel ca- pacity of 1 - H(ε). In particular, for a small enough ε, our result gives the first separation between interactive and non- interactive channel capacity, answering an open problem by Schulman [6]. We complement this result by the lower bound C(ε) ≥ 1-O (√H(ε) ) ; proved for the case where the players take alternating turns.

KW - Com- munication complexity

KW - Information theory

KW - Interactive channel capacity

KW - The entropy function

UR - http://www.scopus.com/inward/record.url?scp=84879805746&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84879805746&partnerID=8YFLogxK

U2 - 10.1145/2488608.2488699

DO - 10.1145/2488608.2488699

M3 - Conference contribution

AN - SCOPUS:84879805746

SN - 9781450320290

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 715

EP - 724

BT - STOC 2013 - Proceedings of the 2013 ACM Symposium on Theory of Computing

T2 - 45th Annual ACM Symposium on Theory of Computing, STOC 2013

Y2 - 1 June 2013 through 4 June 2013

ER -