On the relation between the index coding and the network coding problems

Salim El Rouayheb, Alex Sprintson, Costas Georghiades

Research output: Chapter in Book/Report/Conference proceedingConference contribution

40 Scopus citations

Abstract

In this paper we show that the Index Coding problem captures several important properties of the more general Network Coding problem. An instance of the Index Coding problem includes a server that holds a set of information messages X = {xl, ..., xk} and a set of receivers R. Each receiver has some side information, known to the server, represented by a subset of X and demands another subset of X. The server uses a noiseless communication channel to broadcast encodings of messages in X to satisfy the receivers' demands. The goal of the server is to find an encoding scheme that requires the minimum number of transmissions. We show that any instance of the Network Coding problem can be efficiently reduced to an instance of the Index Coding problem. Our reduction shows that several important properties of the Network Coding problem carry over to the Index Coding problem. In particular, we prove that both scalar linear and vector linear codes are insufficient for achieving the minimal number of transmissions.

Original languageEnglish (US)
Title of host publicationProceedings - 2008 IEEE International Symposium on Information Theory, ISIT 2008
Pages1823-1827
Number of pages5
DOIs
StatePublished - 2008
Externally publishedYes
Event2008 IEEE International Symposium on Information Theory, ISIT 2008 - Toronto, ON, Canada
Duration: Jul 6 2008Jul 11 2008

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
ISSN (Print)2157-8101

Other

Other2008 IEEE International Symposium on Information Theory, ISIT 2008
CountryCanada
CityToronto, ON
Period7/6/087/11/08

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Information Systems
  • Modeling and Simulation
  • Applied Mathematics

Fingerprint Dive into the research topics of 'On the relation between the index coding and the network coding problems'. Together they form a unique fingerprint.

Cite this