Title	Network Coding and the Capacity of Information Networks
Speaker	Dr. Bobby Kleinberg
Time	Monday, December 5, 3:00pm
Location	SSL 150

Abstract

What is the maximum rate at which a set of sender-receiver pairs can simultaneously transmit data in a network with error-free links of finite capacity? Surprisingly, this fundamental question has never been answered. When the nodes of the network are viewed as routers which only forward packets without modifying their contents, the question becomes a multicommodity network flow problem and its solution is completely understood. However, when nodes are allowed to perform non-trivial encoding operations on the data (e.g. transmitting the XOR of two received bits) it may be possible to achieve a higher transmission rate. Indeed, there are examples of directed graphs where such "network coding solutions" improve significantly on traditional flows. For undirected graphs no such examples are known. I will present some recent results and open problems in this area, guided by the following questions:

1. How is the network coding rate related to the multicommodity flow rate of a network?
2. In undirected graphs, are these two rates always equal?
3. How is the network coding rate related to combinatorial parameters such as the sparsest cut in a network?

I will introduce a technique for proving upper bounds on the network coding rate, which allows us to obtain partial answers to some of these questions. In particular, I will exhibit an infinite family of undirected graphs in which the network coding rate is provably less than the sparsest-cut bound. I will also show that an affirmative answer to the second question would imply lower bounds settling long-standing open questions about the complexity of matrix transposition.

This is joint work with Micah Adler, Nick Harvey, Kamal Jain, and April Lehman.