A Caltech Library Service

An Equivalence between Network Coding and Index Coding

Effros, Michelle and El Rouayheb, Salim and Langberg, Michael (2015) An Equivalence between Network Coding and Index Coding. IEEE Transactions on Information Theory, 61 (5). pp. 2478-2487. ISSN 0018-9448.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


We show that the network coding and index coding problems are equivalent. This equivalence holds in the general setting which includes linear and non-linear codes. Specifically, we present a reduction that maps a network coding instance to an index coding instance while preserving feasibility, i.e., the network coding instance has a feasible solution if and only if the corresponding index coding instance is feasible. In addition, we show that one can determine the capacity region of a given network coding instance with colocated sources by studying the capacity region of a corresponding index coding instance. Previous connections between network and index coding were restricted to the linear case.

Item Type:Article
Related URLs:
URLURL TypeDescription
Langberg, Michael0000-0002-7470-0718
Additional Information:© 2015 IEEE. This material is based upon work supported by ISF grant 480/08, BSF grant 2010075, and NSF grants CCF-1018741 and CCF-1016671. The work was done while Michael Langberg was visiting the California Institute of Technology. S. El Rouayheb would like to thank Prof. Vincent Poor for his continuous support, and Curt Schieler for interesting discussions on the index coding problem.
Funding AgencyGrant Number
Israel Science Foundation (ISF)480/08
Binational Science Foundation (USA-Israel)2010075
Issue or Number:5
Record Number:CaltechAUTHORS:20150324-094743353
Persistent URL:
Official Citation:Effros, M.; El Rouayheb, S.; Langberg, M., "An Equivalence Between Network Coding and Index Coding," Information Theory, IEEE Transactions on , vol.61, no.5, pp.2478,2487, May 2015 doi: 10.1109/TIT.2015.2414926 URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:56011
Deposited By: Tony Diaz
Deposited On:24 Mar 2015 16:57
Last Modified:09 Mar 2020 13:18

Repository Staff Only: item control page