^February March – 2009 ^April

Consider the problem of lossless source coding for networks with side information. This model captures scenarios where the network capacity is insufficient to describe the source to its intended destinations, yet, it can still be delivered without loss provided there is sufficient capacity from a helper. The problem of source coding with side information has numerous applications, from sensor networks, where transmission occurs through nodes which may have correlated data, to multimedia networks, where intermediate nodes may have, for example, a lower-resolution version of the required information.

While several spacial cases of this problem have been addressed in the current literature (e.g., the three-node network of Ahlswede and Korner), the general problem remains unsolved. In this work, we derive inner and outer bounds on the rate region and describe sufficient conditions for the tightness of these bounds. Our approach demonstrates how strategies intended for small canonical problems, combined with network coding, can tackle complex networks, while still inheriting the desirable properties of the building blocks used. Furthermore, due to the complexity of solving large networks, it is highly desirable to identify the key parameters which dictate their rate region. This work substantially extends the network scenarios for which maxflow-mincut analysis is know to describe the rate region in full. Finally, in this work we open a new connection between networking and successive refinement of information.

Joint work with Salman Avestimehr and Michelle Effros.