On the relationship between edge removal and strong converses

Oliver Kosut; Jorg Kliewer

doi:10.1109/ISIT.2016.7541605

On the relationship between edge removal and strong converses

Oliver Kosut, Jorg Kliewer

Electrical and Computer Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

3 Scopus citations

Abstract

This paper explores the relationship between two ideas in network information theory: edge removal and strong converses. Edge removal properties state that if an edge of small capacity is removed from a network, the capacity region does not change too much. Strong converses state that, for rates outside the capacity region, the probability of error converges to 1. Various notions of edge removal and strong converse are defined, depending on how edge capacity and residual error probability scale with blocklength, and relations between them are proved. In particular, each class of strong converse implies a specific class of edge removal. The opposite direction is proved for deterministic networks, and some discussion is given for the noisy case.

Original language	English (US)
Title of host publication	Proceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	1779-1783
Number of pages	5
ISBN (Electronic)	9781509018062
DOIs	https://doi.org/10.1109/ISIT.2016.7541605
State	Published - Aug 10 2016
Event	2016 IEEE International Symposium on Information Theory, ISIT 2016 - Barcelona, Spain Duration: Jul 10 2016 → Jul 15 2016

Publication series

Name	IEEE International Symposium on Information Theory - Proceedings
Volume	2016-August
ISSN (Print)	2157-8095

Other

Other	2016 IEEE International Symposium on Information Theory, ISIT 2016
Country/Territory	Spain
City	Barcelona
Period	7/10/16 → 7/15/16

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Information Systems
Modeling and Simulation
Applied Mathematics

Access to Document

10.1109/ISIT.2016.7541605

Cite this

Kosut, O., & Kliewer, J. (2016). On the relationship between edge removal and strong converses. In Proceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory (pp. 1779-1783). Article 7541605 (IEEE International Symposium on Information Theory - Proceedings; Vol. 2016-August). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ISIT.2016.7541605

@inproceedings{c4c4fc92e1d14490a1f1e9e2ee71ee76,

title = "On the relationship between edge removal and strong converses",

abstract = "This paper explores the relationship between two ideas in network information theory: edge removal and strong converses. Edge removal properties state that if an edge of small capacity is removed from a network, the capacity region does not change too much. Strong converses state that, for rates outside the capacity region, the probability of error converges to 1. Various notions of edge removal and strong converse are defined, depending on how edge capacity and residual error probability scale with blocklength, and relations between them are proved. In particular, each class of strong converse implies a specific class of edge removal. The opposite direction is proved for deterministic networks, and some discussion is given for the noisy case.",

author = "Oliver Kosut and Jorg Kliewer",

note = "Funding Information: This material is based upon work supported by the National Science Foundation under grants CCF-1422358 and CNS-1526547 Publisher Copyright: {\textcopyright} 2016 IEEE.; 2016 IEEE International Symposium on Information Theory, ISIT 2016 ; Conference date: 10-07-2016 Through 15-07-2016",

year = "2016",

month = aug,

day = "10",

doi = "10.1109/ISIT.2016.7541605",

language = "English (US)",

series = "IEEE International Symposium on Information Theory - Proceedings",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "1779--1783",

booktitle = "Proceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory",

address = "United States",

}

Kosut, O & Kliewer, J 2016, On the relationship between edge removal and strong converses. in Proceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory., 7541605, IEEE International Symposium on Information Theory - Proceedings, vol. 2016-August, Institute of Electrical and Electronics Engineers Inc., pp. 1779-1783, 2016 IEEE International Symposium on Information Theory, ISIT 2016, Barcelona, Spain, 7/10/16. https://doi.org/10.1109/ISIT.2016.7541605

On the relationship between edge removal and strong converses. / Kosut, Oliver; Kliewer, Jorg.
Proceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory. Institute of Electrical and Electronics Engineers Inc., 2016. p. 1779-1783 7541605 (IEEE International Symposium on Information Theory - Proceedings; Vol. 2016-August).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - On the relationship between edge removal and strong converses

AU - Kosut, Oliver

AU - Kliewer, Jorg

PY - 2016/8/10

Y1 - 2016/8/10

N2 - This paper explores the relationship between two ideas in network information theory: edge removal and strong converses. Edge removal properties state that if an edge of small capacity is removed from a network, the capacity region does not change too much. Strong converses state that, for rates outside the capacity region, the probability of error converges to 1. Various notions of edge removal and strong converse are defined, depending on how edge capacity and residual error probability scale with blocklength, and relations between them are proved. In particular, each class of strong converse implies a specific class of edge removal. The opposite direction is proved for deterministic networks, and some discussion is given for the noisy case.

AB - This paper explores the relationship between two ideas in network information theory: edge removal and strong converses. Edge removal properties state that if an edge of small capacity is removed from a network, the capacity region does not change too much. Strong converses state that, for rates outside the capacity region, the probability of error converges to 1. Various notions of edge removal and strong converse are defined, depending on how edge capacity and residual error probability scale with blocklength, and relations between them are proved. In particular, each class of strong converse implies a specific class of edge removal. The opposite direction is proved for deterministic networks, and some discussion is given for the noisy case.

UR - http://www.scopus.com/inward/record.url?scp=84985945074&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84985945074&partnerID=8YFLogxK

U2 - 10.1109/ISIT.2016.7541605

DO - 10.1109/ISIT.2016.7541605

M3 - Conference contribution

AN - SCOPUS:84985945074

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 1779

EP - 1783

BT - Proceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2016 IEEE International Symposium on Information Theory, ISIT 2016

Y2 - 10 July 2016 through 15 July 2016

ER -

On the relationship between edge removal and strong converses

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this