On the index coding problem and its relation to network coding and matroid theory

Salim El Rouayheb, Alex Sprintson, Costas Georghiades

Research output: Contribution to journalArticle

174 Citations (Scopus)

Abstract

The index coding problem has recently attracted a significant attention from the research community due to its theoretical significance and applications in wireless ad hoc networks. An instance of the index coding problem includes a sender that holds a set of information messages $X=\{x1 〉 ̇ ̇ ̇ 〉xk } and a set of receivers R. Each receiver ρ=(x,H) in R needs to obtain a message x E X and has prior side information consisting of a subset H of X. The sender uses a noiseless communication channel to broadcast encoding of messages in X to all clients. The objective is to find an encoding scheme that minimizes the number of transmissions required to satisfy the demands of all the receivers. In this paper, we analyze the relation between the index coding problem, the more general network coding problem, and the problem of finding a linear representation of a matroid. In particular, we show that any instance of the network coding and matroid representation problems can be efficiently reduced to an instance of the index coding problem. Our reduction implies that many important properties of the network coding and matroid representation problems carry over to the index coding problem. Specifically, we show that vector linear codes outperform scalar linear index codes and that vector linear codes are insufficient for achieving the optimum number of transmissions.

Original languageEnglish (US)
Article number5484982
Pages (from-to)3187-3195
Number of pages9
JournalIEEE Transactions on Information Theory
Volume56
Issue number7
DOIs
StatePublished - Jul 1 2010

Fingerprint

Network coding
coding
Wireless ad hoc networks
recipient
broadcast
communication

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Keywords

  • Index coding
  • Matroid theory
  • Network coding
  • Nonlinear codes
  • Side information

Cite this

@article{0ae01c670b7a4a3c87d271937088244d,
title = "On the index coding problem and its relation to network coding and matroid theory",
abstract = "The index coding problem has recently attracted a significant attention from the research community due to its theoretical significance and applications in wireless ad hoc networks. An instance of the index coding problem includes a sender that holds a set of information messages $X=\{x1 〉 ̇ ̇ ̇ 〉xk } and a set of receivers R. Each receiver ρ=(x,H) in R needs to obtain a message x E X and has prior side information consisting of a subset H of X. The sender uses a noiseless communication channel to broadcast encoding of messages in X to all clients. The objective is to find an encoding scheme that minimizes the number of transmissions required to satisfy the demands of all the receivers. In this paper, we analyze the relation between the index coding problem, the more general network coding problem, and the problem of finding a linear representation of a matroid. In particular, we show that any instance of the network coding and matroid representation problems can be efficiently reduced to an instance of the index coding problem. Our reduction implies that many important properties of the network coding and matroid representation problems carry over to the index coding problem. Specifically, we show that vector linear codes outperform scalar linear index codes and that vector linear codes are insufficient for achieving the optimum number of transmissions.",
keywords = "Index coding, Matroid theory, Network coding, Nonlinear codes, Side information",
author = "{El Rouayheb}, Salim and Alex Sprintson and Costas Georghiades",
year = "2010",
month = "7",
day = "1",
doi = "10.1109/TIT.2010.2048502",
language = "English (US)",
volume = "56",
pages = "3187--3195",
journal = "IEEE Transactions on Information Theory",
issn = "0018-9448",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "7",

}

On the index coding problem and its relation to network coding and matroid theory. / El Rouayheb, Salim; Sprintson, Alex; Georghiades, Costas.

In: IEEE Transactions on Information Theory, Vol. 56, No. 7, 5484982, 01.07.2010, p. 3187-3195.

Research output: Contribution to journalArticle

TY - JOUR

T1 - On the index coding problem and its relation to network coding and matroid theory

AU - El Rouayheb, Salim

AU - Sprintson, Alex

AU - Georghiades, Costas

PY - 2010/7/1

Y1 - 2010/7/1

N2 - The index coding problem has recently attracted a significant attention from the research community due to its theoretical significance and applications in wireless ad hoc networks. An instance of the index coding problem includes a sender that holds a set of information messages $X=\{x1 〉 ̇ ̇ ̇ 〉xk } and a set of receivers R. Each receiver ρ=(x,H) in R needs to obtain a message x E X and has prior side information consisting of a subset H of X. The sender uses a noiseless communication channel to broadcast encoding of messages in X to all clients. The objective is to find an encoding scheme that minimizes the number of transmissions required to satisfy the demands of all the receivers. In this paper, we analyze the relation between the index coding problem, the more general network coding problem, and the problem of finding a linear representation of a matroid. In particular, we show that any instance of the network coding and matroid representation problems can be efficiently reduced to an instance of the index coding problem. Our reduction implies that many important properties of the network coding and matroid representation problems carry over to the index coding problem. Specifically, we show that vector linear codes outperform scalar linear index codes and that vector linear codes are insufficient for achieving the optimum number of transmissions.

AB - The index coding problem has recently attracted a significant attention from the research community due to its theoretical significance and applications in wireless ad hoc networks. An instance of the index coding problem includes a sender that holds a set of information messages $X=\{x1 〉 ̇ ̇ ̇ 〉xk } and a set of receivers R. Each receiver ρ=(x,H) in R needs to obtain a message x E X and has prior side information consisting of a subset H of X. The sender uses a noiseless communication channel to broadcast encoding of messages in X to all clients. The objective is to find an encoding scheme that minimizes the number of transmissions required to satisfy the demands of all the receivers. In this paper, we analyze the relation between the index coding problem, the more general network coding problem, and the problem of finding a linear representation of a matroid. In particular, we show that any instance of the network coding and matroid representation problems can be efficiently reduced to an instance of the index coding problem. Our reduction implies that many important properties of the network coding and matroid representation problems carry over to the index coding problem. Specifically, we show that vector linear codes outperform scalar linear index codes and that vector linear codes are insufficient for achieving the optimum number of transmissions.

KW - Index coding

KW - Matroid theory

KW - Network coding

KW - Nonlinear codes

KW - Side information

UR - http://www.scopus.com/inward/record.url?scp=77953735305&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77953735305&partnerID=8YFLogxK

U2 - 10.1109/TIT.2010.2048502

DO - 10.1109/TIT.2010.2048502

M3 - Article

AN - SCOPUS:77953735305

VL - 56

SP - 3187

EP - 3195

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

SN - 0018-9448

IS - 7

M1 - 5484982

ER -