CAM colloquium - January 30

Sergio Servetto
Electrical and Computer Engineering
Cornell University

"Network Flow Methods in Information Theory"

When does information, as defined by Shannon, behave like a flow in a network setup? In this talk, I will argue that far more often than common wisdom would suggest. We will see how, for a large (and arguably most relevant in practice) class of problems involving distributed sources and channels, all of the following statements hold:

a) There exists a solution to the problem of transporting the sources over the channels *if and only if* a suitably defined multicommodity flow is feasible.

b) If a solution exists, then a solution exists based on separate network source and channel coding only.

c) When multiple solutions exist, under a natural linear cost model, an optimal solution takes the form of a minimum-cost multicommodity flow.

Based on these results, we can make a number of statements about what constitutes an optimal system architecture for an important class of communication networks, where optimality is defined in a pure information theoretic sense, but has a very clear and intuitive network flow interpretation.