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 -