CaltechAUTHORS
  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. https://resolver.caltech.edu/CaltechAUTHORS:20191031-124927142

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

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20191031-124927142

Abstract

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
https://doi.org/10.1109/tit.2019.2949803DOIArticle
ORCID:
AuthorORCID
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.
Funders:
Funding AgencyGrant Number
Israel Science Foundation480/08
Binational Science Foundation (USA-Israel)2010075
NSFCCF-1321129
NSFCCF-1526771
Subject Keywords:Network coding, edge-removal, source cooperation, zero-error
Issue or Number:2
Record Number:CaltechAUTHORS:20191031-124927142
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20191031-124927142
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
Collection:CaltechAUTHORS
Deposited By: George Porter
Deposited On:31 Oct 2019 20:08
Last Modified:21 Jan 2020 19:00

Repository Staff Only: item control page