Events — Colloquia & Seminars
Network Capacity
Speaker: April Rasala Lehman, MIT
Date: Friday, March 18, 2005
Talk: 3:15 PM, 164 WVH
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 (orinformation) 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.
Brief Biography
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.