2013/01/22 by Karthikeyan Shanmugam, Alexandros G. Dimakis, Shanmugam, Karthikeyan +3 · 6 citations
Computer Science · Mathematics · #Caching and Content Delivery #Cooperative Communication and Network Coding #Discrete Mathematics (cs.DM) #Error Correcting Code Techniques #FOS: Computer and information sciences #Information Theory (cs.IT) #cs.DM #cs.IT #math.IT
paper · pdf · doi:10.48550/arxiv.1301.5359
14 Pages, 3 Figures; A conference version submitted to ISIT 2013; typos corrected
openalex publication_date 2013/01/22 · arxiv created 2013/02/08 · arxiv updated 2013/02/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.