WHAT: ART Seminar

WHEN: Friday, 9/19, 11:30 AM

WHERE: CN 149

TITLE: Network Information Flow

ABSTRACT:

We will discuss a new class of problems in an area referred to as network
information flow.  Consider a point-to-point communication network on
which a number of information sources are to be multicast to certain sets
of destinations.  The goal is to determine the maximum rate of information
transfer from the sources to the destinations, given capacity constraints
on the edges.

We will focus our attention on the special case when there is a single
source and multiple destinations.  Recent results have shown that
information transfer using *coding* within the network yields strictly
greater throughput than without coding.  Furthermore, the rate achieved
with coding in fact matches the size of a min-cut separating the source
from a destination, yielding an elegant max-flow min-cut theorem for
network information flow.  We will review some of the key results in the
area and discuss potential directions for future research.

The discussion will be primarily based on the following 3 papers:

(1) Network Information Flow, Ahlswede et al, IEEE Transactions on
Information Theory 2000

(2) Linear Network Coding, Li et al, IEEE Transactions on Information
Theory 2003

(3) Polynomial Time Algorithms For Network Information Flow, Sanders et
al, SPAA 2003