Gates 104

**Christina Fragouli**
*EPFL, Lausanne*

**About the talk:**

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
This is joint work with Emina Soljanin. |

**About the speaker:**

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. |