[Colloq] Network Capacity by April Rasala Lehman

[Ravi Sundaram]

WVH 164, 3:15 - 4:45, Friday 3/18/05


Title: Network Capacity
------

Abstract:
--------

What is the capacity of a network?  Does capacity depend on what stuff is sent through the network?  For a long time, information networks and

traffic/distribution networks were studied using the same set of
techniques.  However, there are many ways in which information can "flow" through a network that are not captured in such models.  We consider the

capacity of information networks.  We present the first non-trivial outer bound on the rate region of general information networks, answering a

question of Song, Yeung and Cai. This outer bound combines properties of

entropy (or information) with a strong information inequality derived from the structure of the network.  This blend of information theoretic and

graph theoretic arguments generates many interesting results. For example, we give the first known proof of a gap between the sparsity of an

undirected graph and its capacity. Extending this result, we show that

multicommodity flow solutions achieve the capacity in an infinite class

of undirected graphs, thereby making progress on a conjecture of
Li and Li.  

This is joint work with Nick Harvey and Robert Kleinberg.
April Rasala Lehman is a graduate student at MIT.