From Alignment to Acyclic Chains: Lexicographic Performance Bounds for Index Coding

Abstract

In this work, we study the information-theoretic performance bounds for the index coding problem. Recently, weighted alignment chain models were proposed by generalizing the alignment chain model of Maleki et al. This led to derivation of single-letter performance bounds that are strictly tighter than both the well-known maximum acyclic induced subgraph (MAIS) bound and the internal conflict bound. Here, we propose a more general chain model, namely the acyclic chain. Unlike weighted alignment chains that are constructed by individual messages, acyclic chains can deal with set of messages as their components. This allows a recursive development of new performance bounds. The new acyclic chain bounds subsume the weighted alignment chain bounds and can be strictly tighter. Moreover, a key drawback of the weighted alignment chain bounds is that their improvement over the MAIS bound is limited to a fixed constant value that does not scale with the problem size. In contrast, we show that the new acyclic chain bounds have a desired multiplicative property under the lexicographic product of the index coding side information graphs. As such, the gap between these new bounds and the MAIS bound is not fixed, but can be magnified to a multiplicative factor which is polynomial in the problem size. Show more