A generalized cut-set bound for deterministic multi-flow networks and its applications

Ilan Shomorony, A. Salman Avestimehr

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

Abstract

We present a new outer bound for the sum capacity of general multi-unicast deterministic networks. Intuitively, this bound can be understood as applying the cut-set bound to concatenated copies of the original network with a special restriction on the allowed transmit signal distributions. We first study applications to finite-field networks, where we obtain a general outer-bound expression in terms of ranks of the transfer matrices. We then show that, even though our outer bound is for deterministic networks, a result from [1] relating the capacity of AWGN K×K×K networks and the capacity of a deterministic counterpart allows us to establish an outer bound to the DoF of K×K×K wireless networks with general connectivity. This bound is tight in the case of the 'adjacent-cell interference' topology, and yields graph-theoretic necessary and sufficient conditions for K DoF to be achievable in general topologies.

Original languageEnglish (US)
Title of host publication2014 IEEE International Symposium on Information Theory, ISIT 2014
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages271-275
Number of pages5
ISBN (Print)9781479951864
DOIs
StatePublished - 2014
Externally publishedYes
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

Other

Other2014 IEEE International Symposium on Information Theory, ISIT 2014
Country/TerritoryUnited States
CityHonolulu, HI
Period6/29/147/4/14

ASJC Scopus subject areas

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

Fingerprint

Dive into the research topics of 'A generalized cut-set bound for deterministic multi-flow networks and its applications'. Together they form a unique fingerprint.

Cite this