[Colloq] Network Capacity - 3/18/05

[Ravi Sundaram]

Apologies for resending. The earlier email was badly 
formatted and missing a bio.
============================================================

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.

Bio:
----
April Rasala Lehman recently completed her PhD at MIT's Computer
Science and Artificial Intelligence Laboratory under the
guidance of Madhu Sudan.  Her research interests are in
algorithms related to networking, communication, routing,
scheduling, and game theory.