The ``Index Coding'' problem is a special (and in a sense representative) instance of the general problem of network communication via network coding. Index coding encapsulates the ``source coding with side information'' problem in which a single server wishes to communicate with several clients each having different side information. The study of index coding has seen a significant amount of interest recently, as both the capacity and its connections to combinatorial properties of the instance at hand are not fully understood.

In this talk I will discuss three topics related to Index Coding. First, I will address the efficient computation of the scalar linear capacity of index coding instances governed by ``simple structured'' side information (corresponding to outer-planar graphs). Next, I will discuss the scalar linear capacity of index coding solutions with ``randomly structured'' side information. Finally, I will address the potential gap between zero-error and epsilon-error capacity in the index coding setting.

Work joint with Michelle Effros, Ishay Haviv and Yossi Berliner.
