Network Coding: from Graph Theory to Algebraic Geometry

The famous min-cut, max-flow theorem states that a source node can send a commodity through a network to a sink node at the rate determined by the flow of the min-cut separating the source and the sink. Recently it has been shown that by linear re-encoding at nodes in communications networks, the min-cut rate can be also achieved in multicasting to several sinks. Constructing such coding schemes efficiently is the subject of current research. Our idea was to divide the network coding problem into two almost independent problems: one of graph theory and the other of classical channel coding theory and algebraic geometry. This talk will describe our approach to the network coding problem and its strengths in deriving theoretical results and practical codes.