Local Graph Coloring and Index Coding

Abstract

We present a novel upper bound for the optimal index coding rate. Our bound uses a graph theoretic quantity called the local chromatic number. We show how a good local coloring can be used to create a good index code. The local coloring is used as an alignment guide to assign index coding vectors from a general position MDS code. We further show that a natural LP relaxation yields an even stronger index code. Our bounds provably outperform the state of the art on index coding but at most by a constant factor.

14 Pages, 3 Figures; A conference version submitted to ISIT 2013; typos corrected

References in corpus (4)

• Broadcasting with side information
• Index coding via linear programming
• An Equivalence between Network Coding and Index Coding
• Index Coding - An Interference Alignment Perspective

Cited by in corpus (12)

• On the Capacity Region for Index Coding
• Caching and Coded Multicasting: Multiple Groupcast Index Coding
• Index Coding Capacity: How far can one go with only Shannon Inequalities?
• When Does an Ensemble of Matrices with Randomly Scaled Rows Lose Rank?
• A Rate-Distortion Approach to Index Coding
• Index Coding and Network Coding via Rank Minimization
• The Optimality of Partial Clique Covering for Index Coding
• Alignment based Network Coding for Two-Unicast-Z Networks
• Relations between the local chromatic number and its directed version
• Topological Interference Management with Decoded Message Passing
• An Efficient Multiple-Groupcast Coded Multicasting Scheme for Finite Fractional Caching
• Rate $\frac{1}{3}$ Index Coding: Forbidden and Feasible Configurations