Information Flow Decomposition for Network Coding

Speaker: Dr. Christina Fragouli, School of Computer and Communication Sciences, EPFLAbstract: 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.The main idea in this talk is a method to identify structural properties of multicast configurations, by decompositing the information flows into a minimal number of subtrees. This decomposition shows that very different networks are equivalent from the coding point of view, and offers a method to identify such equivalence classes. It also allows us to divide the network coding problem into two almost independent problems: one of graph theory and the other of classical channel coding theory. This approach to network coding enables us to derive tight bounds on the network code alphabet size, calculate the throughput improvement network coding can offer for different configurations. It also allows to develop algorithms to specify the coding operations at network nodes without the knowledge of the overall network topology. Such decentralized designs facilitate the construction of codes which can easily accommodate future changes in the network, e.g., addition of receivers and loss of links.This is joint work with Emina Soljanin.Bio: Christina Fragouli received her PhD from UCLA in Electrical Engineering in Fall 2000. Since then, she has worked at the Information Sciences Center at AT&T Labs (Florham Park, NJ) and at the National Capodistrian University of Athens, as a Research Associate. Currently she holds a postdoctoral position at the School of Computer and Communication Sciences at EPFL. She visited DIMACS (Rutgers University) and Bell Labs (Math. for Communication Dept., Murray Hill, NJ) in Spring 2003.Host: Dr. Urbashi Mitra, ubli@usc.edu

Location: Hedco Neurosciences Building (HNB) - -107

Audiences: Everyone Is Invited

Contact: Mayumi Thrasher