Title:

 

  Some Network Information Theory Problems, as Understood by a CS Student

 

 

Speaker:

 

  Sergio D. Servetto

  School of Electrical and Computer Engineering

  Cornell University

  http://cn.ece.cornell.edu/

 

 

Abstract:

 

According to Shannon, the fundamental problem of communication is that
of reproducing at one point either exactly or approximately a message
selected at another point.  This fundamental problem admits many
different incarnations, and one of them, involving a single
transmitter and a single receiver, at least in a purely discrete
setting, can be considered solved.

But when considering networks of transmitters and receivers, the field
remains wide open.  In this talk, we will look at the structure of
some of these network information theory problems, and we will see how
these are essentially CS theory problems.

 

We will start by revisiting four theorems that solve the
point-to-point communication problem: the channel capacity theorem,
the rate-distortion theorem, the source-channel separation theorem,
and the Blahut-Arimoto algorithm for efficiently computing capacity
and rate-distortion.  These results are of interest because they
provide a concrete and detailed example of the kind of solutions we
would like to obtain for various network setups.

Then we will consider two interesting networks.  In one, we will see
that the question of whether a distributed source of information can
be transported over a network of noisy links reduces to the question
of non-emptyness of a polytope whose number of faces grows
exponentially in network size, and we will give a polynomial-time
algorithm to answer this decision question.  In another, we will see
that the determination of the region of achievable rates in a certain
distributed compression problem involves determining the size of the
largest cover elements in a metric space.  I will conclude my talk by
trying to drive home the point that, at least in the problems I have
thought about so far (and quite likely in general), CS theory and
methods hold the key to their solution.

 

  Parts of this talk are heavily influenced by things I have learned
  in joint work with Joao Barros (U. Porto/CS), and with Ying Li, Mung
  Chiang and Sergio Verdu (Princeton/EE).

 

 

Bio:

 

  Sergio D. Servetto was born in Argentina, on January 18, 1968.  He
  received a Licenciatura en Inform\'atica from Universidad Nacional
  de La Plata (UNLP, Argentina) in 1992, and the M.Sc. degree in
  Electrical Engineering and the Ph.D. degree in Computer Science from
  the University of Illinois at Urbana-Champaign (UIUC), in 1996 and
  1999.  Between 1999 and 2001, he worked at the \'Ecole Polytechnique
  F\'ed\'erale de Lausanne (EPFL), Lausanne, Switzerland.  Since Fall
  2001, he has been an Assistant Professor in the School of Electrical
  and Computer Engineering at Cornell University, and a member of the
  fields of Applied Mathematics and Computer Science.  He was the
  recipient of the 1998 Ray Ozzie Fellowship, given to ``outstanding
  graduate students in Computer Science,'' and of the 1999 David J.
  Kuck Outstanding Thesis Award, for the best doctoral dissertation of
  the year, both from the Dept.\ of Computer Science at UIUC.  He was
  also the recipient of a 2003 NSF CAREER Award.  His research
  interests are centered around information theoretic aspects of
  networked systems, with a current emphasis on problems that arise in
  the context of large-scale sensor networks.