Strong Converses are Just Edge Removal Properties

Oliver Kosut, Jörg Kliewer

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

This paper explores the relationship between two ideas in the 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 as the blocklength goes to infinity. Various notions of edge removal and strong converse are defined, depending on how edge capacity and error probability scale with blocklength, and relations between them are proved. Each class of strong converse implies a specific class of edge removal. The opposite directions are proved for deterministic networks. Furthermore, a technique based on a novel, causal version of the blowing-up lemma is used to prove that for discrete memoryless networks, the weak edge removal property - that the capacity region changes continuously as the capacity of an edge vanishes - is equivalent to the exponentially strong converse - that outside the capacity region, the probability of error goes to 1 exponentially fast. This result is used to prove exponentially strong converses for several examples, including the discrete two-user interference channel with strong interference, with only a small variation from traditional weak converse proofs.

Original languageEnglish (US)
Article number8589022
Pages (from-to)3315-3339
Number of pages25
JournalIEEE Transactions on Information Theory
Volume65
Issue number6
DOIs
StatePublished - Jun 2019

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Keywords

  • Strong converse
  • blowing-up lemma
  • edge removal
  • network information theory
  • reduction results

Fingerprint Dive into the research topics of 'Strong Converses are Just Edge Removal Properties'. Together they form a unique fingerprint.

Cite this