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. 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: |
| ||||||||||
| ORCID: |
| ||||||||||
| 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: |
| ||||||||||
| Subject Keywords: | Network coding, edge-removal, source cooperation, zero-error | ||||||||||
| Issue or Number: | 2 | ||||||||||
| DOI: | 10.1109/tit.2019.2949803 | ||||||||||
| 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: | 16 Nov 2021 17:47 |
Repository Staff Only: item control page
