Equivalence for networks with adversarial state

Oliver Kosut, Jörg Kliewer

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations


We address the problem of finding the capacity of networks with independent point-to-point channels where a subset of these channels is replaced either by a compound channel (CC) or an arbitrarily varying channel (AVC). These channels represent a good model for the presence of a Byzantine adversary which controls a subset of links or nodes in the network. We show that equivalence between this network and another network hold in the sense that all links can be replaced by noiseless bit-pipes with the same capacity as the noisy CC or nonsymmetrizable AVC, leading to identical capacity regions for both networks. We then strengthen these results by showing that an additional feedback path between the output and input of a CC or an additional forward path for the AVC extends the equivalent capacity region for both the noisy and the derived noiseless network. This explicitly includes the symmetrizable AVC case.

Original languageEnglish (US)
Title of host publication2014 IEEE International Symposium on Information Theory, ISIT 2014
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages5
ISBN (Print)9781479951864
StatePublished - 2014
Event2014 IEEE International Symposium on Information Theory, ISIT 2014 - Honolulu, HI, United States
Duration: Jun 29 2014Jul 4 2014

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
ISSN (Print)2157-8095


Other2014 IEEE International Symposium on Information Theory, ISIT 2014
Country/TerritoryUnited States
CityHonolulu, HI

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Information Systems
  • Modeling and Simulation
  • Applied Mathematics


Dive into the research topics of 'Equivalence for networks with adversarial state'. Together they form a unique fingerprint.

Cite this