2017/11/17 by Ashok Choudhury, Choudhary, Ashok, Vamsi Krishna Gummadi +3
Computer Science · #Combinatorics (math.CO) #Cooperative Communication and Network Coding #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT)
paper · pdf · doi:10.48550/arxiv.1711.06487
openalex publication_date 2017/11/17 · openalex created_date 2022/10/06 · openalex updated_date 2026/07/28
In Index Coding, the goal is to use a broadcast channel as efficiently as\npossible to communicate information from a source to multiple receivers which\ncan possess some of the information symbols at the source as side-information.\nIn this work, we present a duality relationship between index coding (IC) and\nmultiple-unicast network coding (NC). It is known that the IC problem can be\nrepresented using a side-information graph G (with number of vertices n\nequal to the number of source symbols). The size of the maximum acyclic induced\nsubgraph, denoted by MAIS is a lower bound on the \broadcast rate.\nFor IC problems with MAIS=n-1 and MAIS=n-2, prior work has shown that\nbinary (over mathbb F2) linear index codes achieve the MAIS lower bound\nfor the broadcast rate and thus are optimal. In this work, we use the the\nduality relationship between NC and IC to show that for a class of IC problems\nwith MAIS=n-3, binary linear index codes achieve the MAIS lower bound on\nthe broadcast rate. In contrast, it is known that there exists IC problems with\nMAIS=n-3 and optimal broadcast rate strictly greater than MAIS.\n