The Edge-Removal Problem's Connections to the Zero-Error and δ-Dependence Problems in Network Coding
- Creators
-
Langberg, Michael
- Effros, Michelle
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.
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.Additional details
- Eprint ID
- 99590
- Resolver ID
- CaltechAUTHORS:20191031-124927142
- 480/08
- Israel Science Foundation
- 2010075
- Binational Science Foundation (USA-Israel)
- CCF-1321129
- NSF
- CCF-1526771
- NSF
- Created
-
2019-10-31Created from EPrint's datestamp field
- Updated
-
2021-11-16Created from EPrint's last_modified field