CaltechAUTHORS
  A Caltech Library Service

A Local Perspective on the Edge Removal Problem

Wei, Fei and Langberg, Michael and Effros, Michelle (2019) A Local Perspective on the Edge Removal Problem. In: 2019 IEEE International Symposium on Information Theory (ISIT). IEEE , Piscataway, NJ, pp. 191-195. ISBN 9781538692912. https://resolver.caltech.edu/CaltechAUTHORS:20191004-100329963

[img] PDF - Submitted Version
See Usage Policy.

598Kb

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

Abstract

The edge removal problem studies the loss in network coding rates that results when a network communication edge is removed from a given network. It is known, for example, that in networks restricted to linear coding schemes and networks restricted to Abelian group codes, removing an edge e^∗ with capacity R_(e^∗) reduces the achievable rate on each source by no more than R_(e^∗). In this work, we seek to uncover larger families of encoding functions for which the edge removal statement holds. We take a local perspective: instead of requiring that all network encoding functions satisfy certain restrictions (e.g., linearity), we limit only the function carried on the removed edge e^∗. Our central results give sufficient conditions on the function carried by edge e^∗ in the code used to achieve a particular rate vector under which we can demonstrate the achievability of a related rate vector once e^∗ is removed.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
https://doi.org/10.1109/isit.2019.8849282DOIArticle
https://arxiv.org/abs/1907.01133arXivDiscussion Paper
ORCID:
AuthorORCID
Langberg, Michael0000-0002-7470-0718
Additional Information:© 2019 IEEE. Work supported in part by NSF grants CCF-1526771, CCF-1527524 and CCF-1817241.
Funders:
Funding AgencyGrant Number
NSFCCF-1526771
NSFCCF-1527524
NSFCCF-1817241
Record Number:CaltechAUTHORS:20191004-100329963
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20191004-100329963
Official Citation:F. Wei, M. Langberg and M. Effros, "A Local Perspective on the Edge Removal Problem," 2019 IEEE International Symposium on Information Theory (ISIT), Paris, France, 2019, pp. 191-195. doi: 10.1109/ISIT.2019.8849282
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:99071
Collection:CaltechAUTHORS
Deposited By: George Porter
Deposited On:04 Oct 2019 20:06
Last Modified:04 Oct 2019 20:06

Repository Staff Only: item control page