"Network Equivalence: Towards Computational Tools for Bounding Network Capacities"

Michelle Effros, Professor of Electrical Engineering, California Institute of Technology

April 21st (Thursday), 11:00am
Harold Frank Hall (HFH), Rm 4164

NOTE: new time and location above

From its inception, the field of information theory has sought tools for calculating the capacities of communication networks. Since direct calculation of capacities for large networks is difficult, most research focuses on the investigation of network components in isolation. For example, Shannon studied a single wireline channel in order to gain insight into landline telephone networks. Similarly, later researchers investigated broadcast, multiple access, and interference channels as a step towards understanding wireless networks. Unfortunately, the capacity of a network cannot be determined, in general, from the capacities of the channels from which it is built. As a result, information theory currently offers no means for calculating capacities for most large networks. Even a path towards the development of such tools remains unclear.

This talk explores a family of new tools for bounding network capacities. While precise component capacities cannot be combined to determine the capacity of networks built from those channels, this work shows that it is possible to derive upper and lower bounds on channel behavior in a manner that guarantees such a modular approach. That is, combining the upper bounds on a network’s component channels guarantees an upper bound on the network capacity, and combining the lower bounds on the same component channels guarantees a lower bound on the network capacity. The resulting approach suggests a new path toward the development of systematic computational tools for bounding capacities of large networks.

About Michelle Effros:

Michelle Effros is a Professor of Electrical Engineering at the California Institute of Technology. Her central research focus is in information theory, with interests in compression, network coding, and network capacity.

Hosted by: Professor Jerry Gibson