Abstract

In this talk, I will present some recent new bounds on the reliability function of the so-called typewriter channels, which represent the prototypical example of channels with a positive zero-error capacity. The main goal is to discuss some interesting challenges which appear when attempting to bound the error exponent for channel coding near the zero-error capacity and highlight some open problems. The lower bound is based on a Gilbert-Varshamov like procedure and improves Gallager’s expurgated bound (even in its multiletter form). The lower bounds is based on a combination of Lovász’s bound on graph capacity with linear programming bounds on the minimum distance/spectrum of codes in Hamming spaces.

BIO: Marco Dalai is an associate professor in the Department of Information Engineering at the University of Brescia, Italy. He received his Laurea degree in Electronics Engineering and his PhD in Information Engineering both from University of Brescia in 2003 and 2007, respectively. His research interests include information theory and related problems in inference and combinatorics. He received the 2014 IEEE Information Theory Society Paper Award.