A Caltech Library Service

The Edge-Removal Problem’s Connections to the Zero-Error and δ-Dependence Problems in Network Coding

Langberg, Michael and Effros, Michelle (2020) The Edge-Removal Problem’s Connections to the Zero-Error and δ-Dependence Problems in Network Coding. IEEE Transactions on Information Theory, 66 (2). pp. 900-913. ISSN 0018-9448. doi:10.1109/tit.2019.2949803.

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

Use this Persistent URL to link to this item:


The edge-removal problem addresses the loss in capacity obtained by the removal of an edge of capacity λ from a given network. In the context of network coding, the edge-removal problem has been solved for certain families of networks (such as instances with co-located sources). However, the problem is open for general instances. This work ties the edge-removal problem to two additional problems in the context of network communication: (a) the “ zero-error” network coding problem, which asks whether the zero-error network coding capacity differs from the capacity when error probability is allowed to tend to zero as the blocklength grows; and (b) the “δ-dependence” problem, which measures the advantage of message dependence in network coding capacity.

Item Type:Article
Related URLs:
URLURL TypeDescription
Langberg, Michael0000-0002-7470-0718
Additional Information:© 2019 IEEE. Manuscript received November 5, 2016; revised December 23, 2018; accepted October 1, 2019. Date of publication October 28, 2019; date of current version January 20, 2020. This work was supported in part by the Israel Science Foundation (ISF) under Grant 480/08, in part by the US-Israel Binational Science Foundation (BSF) under Grant 2010075, and in part by the National Science Foundation (NSF) under Grant CCF-1321129 and Grant CCF-1526771. This article was presented in part at the 2011 49th Annual Allerton Conference on Communication, Control, and Computing, and in part at the 2012 IEEE Information Theory Workshop.
Funding AgencyGrant Number
Israel Science Foundation480/08
Binational Science Foundation (USA-Israel)2010075
Subject Keywords:Network coding, edge-removal, source cooperation, zero-error
Issue or Number:2
Record Number:CaltechAUTHORS:20191031-124927142
Persistent URL:
Official Citation:M. Langberg and M. Effros, "The Edge-Removal Problem’s Connections to the Zero-Error and δ-Dependence Problems in Network Coding," in IEEE Transactions on Information Theory, vol. 66, no. 2, pp. 900-913, Feb. 2020. doi: 10.1109/TIT.2019.2949803
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:99590
Deposited By: George Porter
Deposited On:31 Oct 2019 20:08
Last Modified:16 Nov 2021 17:47

Repository Staff Only: item control page