Title: Network Capacity
Speaker: April Rasala Lehman (MIT CSAIL)
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.