Combinatorics Seminar
When: Sunday, May 29, 10am
Where: Schreiber 309
Speaker: Eyal Lubetzky, Microsoft Research
Title: Optimal graph index coding
Abstract:
In the Index Coding problem a server holds a set of messages that it
wishes to broadcast to a set of receivers. Each receiver is interested in
one of the messages and has side-information consisting of some subset
of the other messages. Given the side-information map as an input,
the objective is to devise an optimal encoding scheme for the messages
(i.e., one minimizing the broadcast length) that allows all the receivers
to retrieve their required information.
The basic setting of Index Coding encodes the side-information map,
the problem input, as an undirected graph and the fundamental parameter
is then the limiting optimal broadcast rate as the message length tends
to infinity. This parameter was unknown even for fairly small graphs,
e.g. a cycle on 5 vertices.
I will review connections of this problem to notions from Extremal
Graph Theory, featured in previous works with Stav and with Alon et
al, and then proceed to some recent developments in its study using
an information-theoretic analysis, in joint work with Anna Blasiak and
Robert Kleinberg.