Network coding has recently become a rapidly evolving area in Information Theory. We will begin by examining the basic concept behind network coding and contrast it to the conventional routing approach in existing networks. We highlight the capacity gain by allowing each node in a network to re-encode its input information instead of simply storing and forwarding data. We then discuss some recent progress in network coding. A bound on network coding rates is presented that generalizes an edge-cut bound on routing rates. The bound, called a progressive d-separating edge set (or PdE) bound, involves progressively removing edges from a network graph and checking whether certain strengthened d-separation conditions are satisfied. We show that the PdE bound and one of its extensions proves that routing is rate-optimal for multiple unicast sessions on bidirectional ring networks. We further show that the PdE bound improves on a standard cut-set bound for networks with broadcasting, interference, and noise.

This work was done jointly with Serap A. Savari from the University of Michigan, Ann Arbor.

Host: Ashu Sabharwal

Biography of Gerhard Kramer:
Gerhard Kramer received the B.Sc. and M.Sc. degrees in electrical engineering from the University of Manitoba, Winnipeg, Manitoba, Canada, in 1991 and 1992, respectively, and the Dr. sc. techn. (Doktor der Technischen Wissenschaften) degree from the Swiss Federal Institute of Technology (ETH), Zurich, Switzerland, in 1998.