An information-theoretic meta-theorem on edge-cut bounds

Sudeep Kamath, Pramod Viswanath

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

3 Scopus citations


We consider the problem of multiple unicast in wireline networks. Edge-cut based bounds which are simple bounds on the rates achievable by routing flow are not in general, fundamental, i.e. they are not outer bounds on the capacity region. It has been observed that when the problem has some kind of symmetry involved, then flows and edge-cut based bounds are 'close', i.e. within a constant or poly-logarithmic factor of each other. In this paper, we make the observation that in these very cases, such edge-cut based bounds are actually 'close' to fundamental yielding an approximate characterization of the capacity region for these problems. We demonstrate this in the case of k-unicast in undirected networks, k-pair unicast in directed networks with symmetric demands i.e. for every source communicating to a destination at a certain rate, the destination communicates an independent message back to the source at the same rate, and sum-rate of k-groupcast in directed networks, i.e. a group of nodes, each of which has an independent message for every other node in the group. We place our work in context of existing results to suggest a meta-theorem: if there is inherent symmetry either in the network connectivity or in the traffic pattern, then edge-cut bounds are near-fundamental and flows approximately achieve capacity.

Original languageEnglish (US)
Title of host publication2012 IEEE International Symposium on Information Theory Proceedings, ISIT 2012
Number of pages5
StatePublished - 2012
Externally publishedYes
Event2012 IEEE International Symposium on Information Theory, ISIT 2012 - Cambridge, MA, United States
Duration: Jul 1 2012Jul 6 2012

Publication series

NameIEEE International Symposium on Information Theory - Proceedings


Other2012 IEEE International Symposium on Information Theory, ISIT 2012
Country/TerritoryUnited States
CityCambridge, MA

All Science Journal Classification (ASJC) codes

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


Dive into the research topics of 'An information-theoretic meta-theorem on edge-cut bounds'. Together they form a unique fingerprint.

Cite this