Technical Program

Paper Detail

Paper Title Generalized Alignment Chain: Improved Converse Results for Index Coding
Paper IdentifierTU4.R2.2
Authors Yucheng Liu, Parastoo Sadeghi, Australian National University, Australia
Session Index Coding II
Location Saint Germain, Level 3
Session Time Tuesday, 09 July, 16:40 - 18:00
Presentation Time Tuesday, 09 July, 17:00 - 17:20
Manuscript  Click here to download the manuscript
Abstract In this paper, we study the information-theoretic converse for the index coding problem. We generalize the definition for the alignment chain, introduced by Maleki et al., to capture more flexible relations among interfering messages at each receiver. Based on this, we derive improved converse results for the single-server index coding problem. Compared to the maximum acyclic induced subgraph (MAIS) bound, the new bounds are always as tight and can strictly outperform the MAIS bound. They can also be useful for large problems, where the generally tighter polymatroidal bound is computationally impractical. We then extend these new bounds to the multi-server index coding problem. We also present a separate, but related result where we identify a smaller single-server index coding instance, compared to those identified in the literature, for which non-Shannon-type inequalities are necessary to give a tighter converse.