Abstract

Calculating the zero-error capacity of noisy channels is notoriously difficult and is a feat that has not been accomplished even for the Heptagon channel, a channel whose output is the mod-7 sum of its input and noise, with the latter taking on the values 0 and 1 equiprobably. This talk will not solve this problem. Instead, I will consider this problem (and its extensions to general modulo-additive noise channels) in the presence of a rate-limited helper that observes the noise noncausally and can describe it to the encoder or the decoder.

A complete solution of the zero-error capacity with a helper will be presented in the presence of feedback or when the alphabet is a prime number (as for the Heptagon channel). It will be shown that zero-rate help can outperform no-help and even feedback. Moreover, unlike the zero-error capacity without a helper, the zero-error helper capacity can be positive yet smaller than one bit.

Joint work with Yiming Yan.

Bio: Amos Lapidoth received his Ph.D. degree in Electrical Engineering from Stanford University in 1995. In the years 1995-1999 he was an Assistant and Associate Professor at the department of Electrical Engineering and Computer Science at the Massachusetts Institute of Technology (MIT) and was the KDD Career Development Associate Professor in Communications and Technology. Since 1999, he has been Professor of Information Theory at ETH Zurich.