Langberg, Michael and Effros, Michelle (2021) Edge removal in undirected networks. In: 2021 IEEE International Symposium on Information Theory. IEEE , Piscataway, NJ, pp. 1421-1426. ISBN 978-1-5386-8209-8. https://resolver.caltech.edu/CaltechAUTHORS:20200526-155245665
![[img]](https://authors.library.caltech.edu/style/images/fileicons/application_pdf.png) |
PDF
- Submitted Version
See Usage Policy. 371kB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20200526-155245665
Abstract
The edge-removal problem asks whether the removal of a λ-capacity edge from a given network can decrease the communication rate between source-terminal pairs by more than λ. We prove that for undirected networks, removing a λ capacity edge decreases the rate by O(λ). Through previously known reductive arguments, here newly applied to undirected networks, our result implies that the zero-error capacity region of an undirected network equals its vanishing-error capacity region. Whether it is possible to prove similar results for directed networks remains an open question.
| Item Type: | Book Section | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Related URLs: |
| |||||||||
| ORCID: |
| |||||||||
| Additional Information: | © 2021 IEEE. This work is supported in part by NSF grants CCF-1817241 and CCF-1909451. The full version of this work appears in [1]. | |||||||||
| Funders: |
| |||||||||
| DOI: | 10.1109/ISIT45174.2021.9518243 | |||||||||
| Record Number: | CaltechAUTHORS:20200526-155245665 | |||||||||
| Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20200526-155245665 | |||||||||
| Official Citation: | M. Langberg and M. Effros, "Edge removal in undirected networks," 2021 IEEE International Symposium on Information Theory (ISIT), 2021, pp. 1421-1426, doi: 10.1109/ISIT45174.2021.9518243 | |||||||||
| Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | |||||||||
| ID Code: | 103480 | |||||||||
| Collection: | CaltechAUTHORS | |||||||||
| Deposited By: | Tony Diaz | |||||||||
| Deposited On: | 26 May 2020 22:55 | |||||||||
| Last Modified: | 29 Oct 2021 16:59 |
Repository Staff Only: item control page
