TY - GEN

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

AU - Rouayheb, Salim El

AU - Sprintson, Alex

AU - Georghiades, Costas

PY - 2008

Y1 - 2008

N2 - 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.

AB - 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.

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

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

U2 - 10.1109/ISIT.2008.4595303

DO - 10.1109/ISIT.2008.4595303

M3 - Conference contribution

AN - SCOPUS:52349112954

SN - 9781424422579

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 1823

EP - 1827

BT - Proceedings - 2008 IEEE International Symposium on Information Theory, ISIT 2008

T2 - 2008 IEEE International Symposium on Information Theory, ISIT 2008

Y2 - 6 July 2008 through 11 July 2008

ER -