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, except in the special case when nodes of the network are assumed
to only store and forward packets without modifying their contents. (In
this case the question reduces to a maximum concurrent multicommodity flow
problem.) When nodes are allowed to send outgoing messages by combining
two or more incoming messages (e.g. taking the XOR of two packets) the
situation is much less well-understood. There are examples of directed
graphs where such "network coding solutions" achieve a transmission rate
exceeding the maximum concurrent multicommodity flow rate; 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 maximum concurrent
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.